HashMap部分源码实现

哈希表(散列表)是一种非常重要的数据结构，哈希表内部实现兼具了数组和链表的优点，所以它的性能非常好，在平均情况下，散列表执行各种操作的时间复杂度都为O(1)，即常量时间。在使用散列表时，需要避免冲突，这就需要处理好两个问题：1. 较低的装填因子 2. 良好的散列函数
关于Java内部hashMap的实现大概总结如下：

1. 先定义一个内部Node用来储存hash值，键值对和指向下一个Node的指针：

class Node<K,V> {
    int hash;
    K key;
    V value;
    Node<K,V> next;

    public Node(int hash,K key,V value,Node<K,V> next){
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    @Override
    public String toString() {
        String x ="[" + key +":"+ value+ "]";
        return x;
    }
}

2. hashMap的内部是一个位桶数组，数组的每个位置储存一个单向链表来解决冲突问题：

public class HashMap<K,V> {
    private Node[] table;
    private int tableLen = 16;
    private int size;

    public HashMap(){
        table = new Node[tableLen];
    }

    public int size(){
        return size;
    }
    /**
     * 散列函数
     */
    private int getHash(int hashCode,int tableLength){
        return hashCode&(tableLength-1);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("{");
        for (int i=0;i<table.length;i++){
            Node temp = table[i];
            while (temp!=null){
                sb.append(temp.toString()+",");
                temp = temp.next;
            }
        }
        sb.setCharAt(sb.length()-1,'}');
        return sb.toString();
    }

    public void put(K key, V value){
        int index = getHash(key.hashCode(),tableLen);
        Node<K,V> node = new Node<>(index,key,value,null);
        Node temp = table[index];
        if (temp == null){
            table[index] = node;
        } else {
            //遍历链表
            while (temp.next != null){
            //判断key是否重复
                if (temp.key.equals(key)){
                    temp.value = value;
                    break;
                }
                temp = temp.next;
            }
            temp.next = node;
        }
        size++;
    }

    public V  get(K key) {
        int index = getHash(key.hashCode(),tableLen);
        Node<K,V> temp = table[index];
        V value = null;

        if (temp!=null){
            while (temp!=null){
                if (key.equals(temp.key)){
                    value = temp.value;
                    break;
                }
                temp = temp.next;
            }
        }
        return value;
    }
}