大數(shù)據(jù)之什么是Hash表
大數(shù)據(jù)之什么是Hash表，Hash，一般翻譯做“散列”，也有直接音譯為“哈希”的，它是基于快速存取的角度設(shè)計(jì)的，也是一種典型的“空間換時(shí)間”的做法。顧名思義，該數(shù)據(jù)結(jié)構(gòu)可以理解為一個(gè)線性表，但是其中的元素不是緊密排列的，而是可能存在空隙。
1.散列表(Hash table，也叫哈希表)，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)。
也就是說(shuō)，它通過(guò)把關(guān)鍵碼值映射到表中一個(gè)位置來(lái)訪問(wèn)記錄，以加快查找的速度。這個(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è)問(wèn)題就是沖突。所謂沖突，即兩個(gè)元素通過(guò)散列函數(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ù)組中呢。一般情況是通過(guò)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ò)容問(wèn)題,性能較低(轉(zhuǎn)移到更大的哈希表中).
Java默認(rèn)的散列單元大小全部都是2的冪，初始值為16(2的4次冪)。假如16條鏈表中的75%鏈接有數(shù)據(jù)的時(shí)候，則認(rèn)為加載因子達(dá)到默認(rèn)的0.75。HahSet開(kāi)始重新散列，也就是將原來(lái)的散列結(jié)構(gòu)全部拋棄，重新開(kāi)辟一個(gè)散列單元大小為32(2的5次冪)的散列結(jié)果，并重新計(jì)算各個(gè)數(shù)據(jù)的存儲(chǔ)位置。以此類推下去.....
負(fù)載(加載)因子:0.75.-->hash表提供的空間是16 也就是說(shuō)當(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ù)又很少，有的甚至沒(méi)有,所以幾乎沒(méi)有什么迭代的代價(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);
- }
- }
