1，概念

2，冲突-避免

3，冲突-避免-哈希函数设计

4，冲突-避免-负载因子调节​

4，冲突-解决-闭散列

①线性探测

②二次探测

5，冲突-解决-开散列/哈希桶

6，完整代码

负载因子和冲突率的关系粗略演示

# 5，冲突-解决-开散列/哈希桶

``````
static class Node {
public int key;
public int val;
public Node next;

public Node(int key, int val) {
this.key = key;
this.val = val;
}
}

private Node[] array;
public int usedSize;

public HashBucket() {
this.array = new Node[10];
this.usedSize = 0;
}``````

`````` public void put(int key,int val){
int index = key % this.array.length;
Node cur = array[index];
while (cur != null){
if(cur.val == key){
cur.val = val;
return;
}
cur = cur.next;
}
//头插法
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
resize();
}
}
``````
``````public int get(int key) {
//以什么方式存储的  那就以什么方式取
int index = key % this.array.length;
Node cur = array[index];
while (cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;//
}``````

``````public void resize(){

Node[] newArray = new Node[2*this.array.length];
for (int i = 0; i < this.array.length; i++){
Node cur = array[i];
Node curNext = null;
while (cur != null){

curNext = cur.next;
int index = cur.key % newArray.length;
cur.next = newArray[i];
newArray[i] = cur;
cur = curNext.next;
cur = curNext;

}
}
this.array = newArray;
}
``````

# 6，完整代码

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

private Node[] array;
public int usedSize;

public HashBucket() {
this.array = new Node[10];
this.usedSize = 0;
}

public void put(int key,int val) {
//1、确定下标
int index = key % this.array.length;
//2、遍历这个下标的链表
Node cur = array[index];
while (cur != null) {
//更新val
if(cur.key == key) {
cur.val = val;
return;
}
cur = cur.next;
}
//3、cur == null   当前数组下标的 链表  没要key
Node node = new Node(key,val);
node.next = array[index];
array[index] = node;
this.usedSize++;
//4、判断  当前 有没有超过负载因子
//扩容
resize();
}
}

public int get(int key) {
//以什么方式存储的  那就以什么方式取
int index = key % this.array.length;
Node cur = array[index];
while (cur != null) {
if(cur.key == key) {
return cur.val;
}
cur = cur.next;
}
return -1;//
}

return this.usedSize*1.0 / this.array.length;
}

public void resize(){

Node[] newArray = new Node[2*this.array.length];
for (int i = 0; i < this.array.length; i++){
Node cur = array[i];
Node curNext = null;
while (cur != null){

curNext = cur.next;
int index = cur.key % newArray.length;
cur.next = newArray[i];
newArray[i] = cur;
cur = curNext.next;
cur = curNext;

}
}
this.array = newArray;
}

}
``````

THE END