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

[[278251]]

1.散列表(Hash table，也叫哈希表)，是根據關鍵碼值(Key value)而直接進行訪問的數據結構。

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

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

2.hash表擴容的理解

可是當哈希表接近裝滿時,因為數組的擴容問題,性能較低(轉移到更大的哈希表中).

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

負載(加載)因子:0.75.-->hash表提供的空間是16 也就是說當到達12的時候就擴容

3.排重機制的實現

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

4.優點

哈希表的插入和查找是很優秀的.

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

對于插入:數組的插入速度慢,而鏈表的插入速度快.當我們使用哈希表時,不需要更改數組的結構,只需要在找到對應的數組下標后,進入對應的鏈表,操作鏈表即可.所以hash表的整體插入速度也很快.

5.模擬實現代碼

Node類

public class Node { 
// key、value模擬鍵值對的數據 
    public Integer key; 
    public String value; 
    // 下一節點的引用 
    public Node next; 
    public Node() { 
    } 
    public Node(int key, String value) { 
        this.key = key; 
        this.value = value; 
    } 
  
} 

MyLinkedList類

 public class MyLinkedList { 
    // 根節點 
    private Node root; 
  
    public MyLinkedList() { 
        root = new Node(); 
    } 
    /** 
     * 添加數據，key值必須唯一，如果重復值將被覆蓋 
     * @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; 
    } 
  
    /** 
     * 刪除數據 
     * @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; 
    } 
  
    /** 
     * 根據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; 
    } 
  
    /** 
     * 遍歷鏈表，列出所有數據 
     * @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 { 
  
    // 鏈表數組，數組的每一項都是一個鏈表 
    private MyLinkedList[] arr; 
    // 數組的大小 
    private int maxSize; 
  
    /** 
     * 空參構造，默認數組大小為10 
     */ 
    public MyHashMap() { 
        maxSize = 10; 
        arr = new MyLinkedList[maxSize]; 
    } 
  
    /** 
     * 帶參構造，數組大小自定義 
     * @param maxSize 
     */ 
    public MyHashMap(int maxSize) { 
        this.maxSize = maxSize; 
        arr = new MyLinkedList[maxSize]; 
    } 
  
    /** 
     * 添加數據，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); 
    } 
  
    /** 
     * 刪除數據 
     * @param key 
     * @return 
     */ 
    public boolean delete(int key) { 
  
        int index = getHashIndex(key); 
        if(arr[index] != null) { 
            return arr[index].delete(key); 
        } 
        return false; 
    } 
  
    /** 
     * 根據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; 
    } 
  
    /** 
     * 獲取數組下標 
     * @param key 
     * @return 
     */ 
    private int getHashIndex(Integer key) { 
        return key.hashCode() % maxSize; 
    } 
  
    /** 
     * 遍歷數組中所有鏈表的數據 
     * @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(); 
    } 
} 

測試類

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); 
    } 
}