开散列法又叫链地址法(开链法)首先对关键码集合用散列函数计算散列地址具有相同地址的关键码归于同一子 集合每一个子集合称为一个桶各个桶中的元素通过一个单链表链接起来各链表的头结点存储在哈希表中。从上图可以看出开散列中每个桶中放的都是发生哈希冲突的元素。开散列可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索了。代码实现以纯数字为例子实际上hash的key的类型是不固定的这里只是为了展示过程public class HashBuck { public class Node{ int key; int val; Node next; public Node(int key, int val) { this.key key; this.val val; } } //负载因子 private static final double DEFAULT_LOAD_FACTOR 0.75f; Node[] arr new Node[10]; int usedSize 0; //插入值 public void put(int key, int val) { //计算插入的位置例如1和11插入同一个位置 int index key % arr.length; Node cur arr[index]; //若已存在则修改 while(cur ! null){ if(cur.key key){ cur.val val; return; } cur cur.next; } //头插 Node newNode new Node(key, val); newNode.next arr[index]; arr[index] newNode; usedSize; //检测当前负载因子是不是大于0.75 if(doLoadFactor() DEFAULT_LOAD_FACTOR){ resize(); } } //扩容 private void resize() { Node[] newArr new Node[arr.length * 2]; for(int i 0; i arr.length; i){ Node cur arr[i]; while(cur ! null){ int index cur.key % newArr.length; Node curN cur.next; cur.next newArr[index]; newArr[index] cur; cur curN; } } arr newArr; } //计算负载因子 private double doLoadFactor() { return usedSize * 1.0 / arr.length; } //查找 public int getVal(int key) { int index key % arr.length; Node cur arr[index]; while(cur ! null){ if(cur.key key){ return cur.val; } cur cur.next; } return -1; } }值得注意的是扩容方法以1和11为例原数组长度为10翻倍后为20原本11%101现在11%20 11所以11必须放在正确的位置上其他数也一样。