/**
 * 哈希桶解决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;
    }
}