Java 哈希表
在用树实现集合时，我们发现每次找数据都要比较很多次，太慢了。有没有说明方法能不用比较直接找到呢？哈希方法可以。
1.哈希表的介绍
哈希表又叫散列表，是通过哈希函数建立的一个数据结构。
哈希函数是什么呢？
举个例子：
我们定义一组数据{1,5,6,8,7,9};
此时哈希函数是：hash(key) = key % capacity（capacity为存储元素底层空间总的大小）。
2.冲突
还是上面的例子，如果在数据中加入了15，我们发现有问题。因为hash(15)=5跟hash(5)冲突了。对于这种用不同的 key 值，但得到了相同的哈希地址的现象我们叫冲突。
遇见冲突我们要想办法解决这个问题的，这里要明白一点，由于我们给的底层存储空间是有限的，永远无法满足所有情况，因此冲突是无法避免的，我们能做的是降低冲突率。
在哈希函数设计时，我们有几种解决方案：
1.直接定制法：在数据范围已知的情况下使用，且查找的范围比较小且连续，如：存26个字母。函数：hash(key) = A*key + B；
2.除留余数法：地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数。哈希函数：hash(key) = key%p；
3.取满法：仅适用于做算法题中，就是直接取到给定数据范围的最大值。
3.负载因子
先看一下网上的说法：HashMap 负载因子( load factor)，也叫做扩容因子和装载因子，它是 HashMap 在进行扩容时的一个阈值，当 HashMap 中的元素个数超过了容量乘以负载因子时，就会进行扩容。默认的负载因子是 0.75，也就是说当 HashMap 中的元素个数超过了容量的 75% 时，就会进行扩容。
关于为什么负载因子是0.75，现在没有什么官方解释。
4.开散列（哈希桶）
开散列法又叫拉链法，名字通俗易懂，其结构就跟拉链一样，数组内存的是链表头节点的地址。
代码的模拟实现：
public class HashBucket {static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}public Node[] array = new Node[10];public int usedSize;public static final double DEFAULT_LOAD_FACTOR = 0.75f;public void push(int key,int val){int idx=key% array.length;//先判断key是否存在Node cur=array[idx];while(cur!=null){if(cur.key==key){cur.val=val;return ;}cur=cur.next;}//如果不存在Node node=new Node(key, val);node.next=array[idx];array[idx]=node;usedSize++;//看看要不要扩容if(doLoadFactor()>=DEFAULT_LOAD_FACTOR){resize();}}private double doLoadFactor(){//求当前负载因子的值return usedSize*1.0/ array.length;}private void resize(){//建立一个新的数组Node[] newArray = new Node[2*array.length];for (int i = 0; i < array.length; i++) {//遍历每一个节点，把节点分到新的数组里Node cur = array[i];while (cur != null) {int idx = cur.key % newArray.length;Node curN = cur.next;cur.next = newArray[idx];newArray[idx] = cur;cur = curN;}}array = newArray;}public int getVal(int key){int idx=key% array.length;Node cur=array[idx];while(cur!=null){if(cur.key==key){return cur.val;}cur=cur.next;}return -1;}
}