大數(shù)據(jù)之什么是Hash表，Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，它是基于快速存取的角度設(shè)計(jì)的，也是一種典型的“空間換時(shí)間”的做法。顧名思義，該數(shù)據(jù)結(jié)構(gòu)可以理解為一個(gè)線性表，但是其中的元素不是緊密排列的，而是可能存在空隙。

[[278251]]

1.散列表(Hash table，也叫哈希表)，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。

也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，以加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，存放記錄的數(shù)組叫做散列表。比如我們存儲(chǔ)70個(gè)元素，但我們可能為這70個(gè)元素申請(qǐng)了100個(gè)元素的空間。70/100=0.7，這個(gè)數(shù)字稱為負(fù)載(加載)因子。我們之所以這樣做，也 是為了“快速存取”的目的。我們基于一種結(jié)果盡可能隨機(jī)平均分布的固定函數(shù)H為每個(gè)元素安排存儲(chǔ)位置，以達(dá)到快速存取。但是由于此隨機(jī)性，也必然導(dǎo)致一個(gè)問題就是沖突。所謂沖突，即兩個(gè)元素通過散列函數(shù)H得到的地址相同，那么這兩個(gè)元素稱為“同義詞”。這類似于70個(gè)人去一個(gè)有100個(gè)椅子的飯店吃飯。散列函數(shù)的計(jì)算結(jié)果是一個(gè)存儲(chǔ)單位地址，每個(gè)存儲(chǔ)單位稱為“桶”。設(shè)一個(gè)散列表有m個(gè)桶，則散列函數(shù)的值域應(yīng)為[0,m-1]。

這些元素是按照什么樣的規(guī)則存儲(chǔ)到數(shù)組中呢。一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對(duì)數(shù)組長(zhǎng)度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲(chǔ)在數(shù)組下標(biāo)為12的位置

2.hash表擴(kuò)容的理解

可是當(dāng)哈希表接近裝滿時(shí),因?yàn)閿?shù)組的擴(kuò)容問題,性能較低(轉(zhuǎn)移到更大的哈希表中).

Java默認(rèn)的散列單元大小全部都是2的冪，初始值為16(2的4次冪)。假如16條鏈表中的75%鏈接有數(shù)據(jù)的時(shí)候，則認(rèn)為加載因子達(dá)到默認(rèn)的0.75。HahSet開始重新散列，也就是將原來的散列結(jié)構(gòu)全部拋棄，重新開辟一個(gè)散列單元大小為32(2的5次冪)的散列結(jié)果，并重新計(jì)算各個(gè)數(shù)據(jù)的存儲(chǔ)位置。以此類推下去.....

負(fù)載(加載)因子:0.75.-->hash表提供的空間是16 也就是說當(dāng)?shù)竭_(dá)12的時(shí)候就擴(kuò)容

3.排重機(jī)制的實(shí)現(xiàn)

假如我們有一個(gè)數(shù)據(jù)(散列碼76268)，而此時(shí)的HashSet有128個(gè)散列單元，那么這個(gè)數(shù)據(jù)將有可能插入到數(shù)組的第108個(gè)鏈表中(76268%128=108)。但這只是有可能，如果在第108號(hào)鏈表中發(fā)現(xiàn)有一個(gè)老數(shù)據(jù)與新數(shù)據(jù)equals()=true的話，這個(gè)新數(shù)據(jù)將被視為已經(jīng)加入，而不再重復(fù)丟入鏈表。

4.優(yōu)點(diǎn)

哈希表的插入和查找是很優(yōu)秀的.

對(duì)于查找:直接根據(jù)數(shù)據(jù)的散列碼和散列表的數(shù)組大小計(jì)算除余后，就得到了所在數(shù)組的位置，然后再查找鏈表中是否有這個(gè)數(shù)據(jù)即可。因?yàn)閿?shù)組本身查找速度快,所以查找的效率高低體現(xiàn)在鏈表中，但是真實(shí)情況下在一條鏈表中的數(shù)據(jù)又很少，有的甚至沒有,所以幾乎沒有什么迭代的代價(jià)。所以散列表的查找效率建立在散列單元所指向的鏈表中數(shù)據(jù)的多少上.

對(duì)于插入:數(shù)組的插入速度慢,而鏈表的插入速度快.當(dāng)我們使用哈希表時(shí),不需要更改數(shù)組的結(jié)構(gòu),只需要在找到對(duì)應(yīng)的數(shù)組下標(biāo)后,進(jìn)入對(duì)應(yīng)的鏈表,操作鏈表即可.所以hash表的整體插入速度也很快.

5.模擬實(shí)現(xiàn)代碼

Node類

public class Node { 
// key、value模擬鍵值對(duì)的數(shù)據(jù) 
    public Integer key; 
    public String value; 
    // 下一節(jié)點(diǎn)的引用 
    public Node next; 
    public Node() { 
    } 
    public Node(int key, String value) { 
        this.key = key; 
        this.value = value; 
    } 
  
} 

MyLinkedList類

 public class MyLinkedList { 
    // 根節(jié)點(diǎn) 
    private Node root; 
  
    public MyLinkedList() { 
        root = new Node(); 
    } 
    /** 
     * 添加數(shù)據(jù)，key值必須唯一，如果重復(fù)值將被覆蓋 
     * @param key 
     */ 
    public void add(int key, String value) { 
  
        Node newNode = new Node(key, value); 
        Node current = root; 
        while (current.next != null) { 
            if(current.next.key == key) { 
                current.next.value = value; 
                return; 
            } 
            current = current.next; 
        } 
        current.next = newNode; 
    } 
  
    /** 
     * 刪除數(shù)據(jù) 
     * @param key 
     * @return 
     */ 
    public boolean delete(int key) { 
  
        Node current = root; 
        while (current.next != null) { 
            if(current.next.key == key) { 
                current.next = current.next.next; 
                return true; 
            } 
            current = current.next; 
        } 
        return false; 
    } 
  
    /** 
     * 根據(jù)key獲取value 
     * @param key 
     * @return 
     */ 
    public String get(int key) { 
  
        Node current = root; 
        while (current.next != null) { 
            if(current.next.key == key) { 
                return current.next.value; 
            } 
            current = current.next; 
        } 
        return null; 
    } 
  
    /** 
     * 遍歷鏈表，列出所有數(shù)據(jù) 
     * @return 
     */ 
    public String list() { 
  
        String str = ""; 
        Node current = root.next; 
        while (current != null) { 
            str += "(" + current.key + "," + current.value + "),"; 
            current = current.next; 
        } 
        return str; 
    } 
  
    @Override 
    public String toString() { 
        return list(); 
    } 
} 

MyHashMap類

// 哈希表 
public class MyHashMap { 
  
    // 鏈表數(shù)組，數(shù)組的每一項(xiàng)都是一個(gè)鏈表 
    private MyLinkedList[] arr; 
    // 數(shù)組的大小 
    private int maxSize; 
  
    /** 
     * 空參構(gòu)造，默認(rèn)數(shù)組大小為10 
     */ 
    public MyHashMap() { 
        maxSize = 10; 
        arr = new MyLinkedList[maxSize]; 
    } 
  
    /** 
     * 帶參構(gòu)造，數(shù)組大小自定義 
     * @param maxSize 
     */ 
    public MyHashMap(int maxSize) { 
        this.maxSize = maxSize; 
        arr = new MyLinkedList[maxSize]; 
    } 
  
    /** 
     * 添加數(shù)據(jù)，key值必須唯一 
     * @param key 
     * @param value 
     */ 
    public void put(int key, String value) { 
  
        int index = getHashIndex(key); 
        if(arr[index] == null) { 
            arr[index] = new MyLinkedList(); 
        } 
        arr[index].add(key, value); 
    } 
  
    /** 
     * 刪除數(shù)據(jù) 
     * @param key 
     * @return 
     */ 
    public boolean delete(int key) { 
  
        int index = getHashIndex(key); 
        if(arr[index] != null) { 
            return arr[index].delete(key); 
        } 
        return false; 
    } 
  
    /** 
     * 根據(jù)key獲取value 
     * @param key 
     * @return 
     */ 
    public String get(int key) { 
  
        int index = getHashIndex(key); 
        if(arr[index] != null) { 
            return arr[index].get(key); 
        } 
        return null; 
    } 
  
    /** 
     * 獲取數(shù)組下標(biāo) 
     * @param key 
     * @return 
     */ 
    private int getHashIndex(Integer key) { 
        return key.hashCode() % maxSize; 
    } 
  
    /** 
     * 遍歷數(shù)組中所有鏈表的數(shù)據(jù) 
     * @return 
     */ 
    public String list() { 
  
        String str = "[ "; 
        for (int i = 0; i < maxSize; i++) { 
            if(arr[i] != null) { 
                str += arr[i].toString(); 
            } 
        } 
        str = str.substring(0, str.length()-1); 
        str += " ]"; 
        return str; 
    } 
  
    @Override 
    public String toString() { 
        return list(); 
    } 
} 

測(cè)試類

public class Test { 
  
    public static void main(String[] args) { 
  
        MyHashMap map = new MyHashMap(20); 
  
        map.put(5, "aaa"); 
        map.put(8, "bbb"); 
        map.put(3, "ccc"); 
        map.put(8, "bbb"); 
        map.put(2, "ddd"); 
        map.put(9, "eee"); 
  
        System.out.println(map); 
        System.out.println(map.get(3)); 
        System.out.println(map.delete(2)); 
        System.out.println(map); 
    } 
}