/**
* 哈希桶解决hash冲突(哈希桶的模拟实现）（同时实现了哈希查找）
*/
public class HashBuck {
class Node {
int key;
int value;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private Node[] array; //该数字中的每一个下标元素都对应一个链表
private int UsedSize;
private static final double DEFULT_LOAD_FACTOR = 0.75;
public HashBuck(int size) {
array = new Node[size];
}
/**
* 插入元素
* @param key
* @param value
*/
public void put(int key, int value) {
Node node = new Node(key, value);
int index = key % array.length;
Node cur = array[index];
while (cur != null) {
if (cur.key == key) {
cur.value = value; // 如果冲突就替换该结点的值
return;
}
cur = cur.next;
}
// 如果程序走到这里，说明该array[index]所对应的那一列上的key没有和要插入结点的key相冲突的
// 进行第二步——头插(在JDK1.8中采用的是尾插）
node.next = array[index];
array[index] = node;
++UsedSize;
// 检查当前哈希表是否超过了负载因子
if (LoadFactor() >= DEFULT_LOAD_FACTOR) {
// 扩容——遍历数组每个链表的每个结点，重新哈希到新的哈希表当中（面试题）
resize();
}
}
// 扩容 && 对哈希表重新哈希
private void resize() {
Node[] temp = new Node[array.length * 2];
// 遍历原来的数组
for (int i = 0; i < array.length; i++) {
// 获取到当前下标的链表的头结点
Node cur = array[i];
// 遍历这个链表的每个结点
while (cur != null) {
Node curNext = cur.next; // 保存下当前链表的下一个结点
int index = cur.key % temp.length;// 获取到当前的key在新的数组中的下标
cur.next = temp[index];
temp[index] = cur;
cur = curNext; // 如果不提前保存cur.next，经过cur.next = temp[index]，cur.next已经变了
}
}
array = temp; // 将原来数组的引用重新引用新的数组
}
private double LoadFactor() {
return UsedSize * 1 / array.length;
}
/**
* 通过key来获取value
*/
public int get(int key) {
int index = key % array.length;
Node cur = array[index];
// 遍历当前数组下标所对应的链表，在该链表中找key
while (cur != null) {
if (cur.key == key) {
return cur.value;
}
else {
cur = cur.next;
}
}
return  -1;
}
}

public class Demo {
//哈希函数
public static int hash(int value) {
return value % 10;
}
//创建哈希表
public static void creatHash(int [] arr,int [] hashArr) {
int i,index;
//将序列中每个元素存储到哈希表
for (i = 0; i < 5; i++) {
index = hash(arr[i]);
while(hashArr[index % 10] != 0) {
index++;
}
hashArr[index] = arr[i];
}
}
//实现哈希查找算法
public static int hash_serach(int [] hashArr,int value) {
//查找目标元素对应的索引值
int hashAdd = hash(value);
while (hashArr[hashAdd] != value) {    // 如果索引位置不是目标元素，则发生了碰撞
hashAdd = (hashAdd + 1) % 10;       // 根据线性探测法，从索引位置依次向后探测
//如果探测位置为空，或者重新回到了探测开始的位置（即探测了一圈），则查找失败
if (hashArr[hashAdd] == 0 || hashAdd == hash(value)) {
return -1;
}
}
//返回目标元素所在的数组下标
return  hashAdd;
}
public static void main(String[] args) {
int [] arr = new int[] {5, 20, 30, 50, 55};
int[] hashArr = new int[10];
//创建哈希表
creatHash(arr,hashArr);
// 查找目标元素 50 位于哈希表中的位置
int hashAdd = hash_serach(hashArr,50);
if(hashAdd == -1) {
System.out.print("查找失败");
}else {
System.out.print("查找成功，目标元素所在哈希表中的下标为：" + hashAdd);
}
}
}