几个主要的概念

hashmap初始化代码

public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

DEFAULT_INITIAL_CAPACITY=16 初始化大小
DEFAULT_LOAD_FACTOR = 0.75f; 默认负载因子
threshold 下次扩容的临界值，hashmap是两倍扩容的，size>=threshold就会扩容，第一次put值的时候会初始化这个值

private void inflateTable(int toSize) {
        // Find a power of 2 >= toSize
        int capacity = roundUpToPowerOf2(toSize);
        threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);  //这里计算出临界值 两个相乘
        table = new Entry[capacity];
        initHashSeedAsNeeded(capacity);
    }

table = (Entry<K,V>[]) EMPTY_TABLE; 存储数据的数组 ,所谓的hash桶指的就是这个数组，因为里面的index位置是根据hash值算出来的，具体看后面

hashmap存储结构

hashmap里面的存储结构用的是一个内部类Entry里面有key,value,hash,next等属性存储值，hashmap定义了一个table[Entry]数组进行存储，next指向的是下一个值位置，主要用的是数组加链表实现具代看put代码

 public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold); //初始化table数组，大小之类的
        }
        if (key == null)
            return putForNullKey(value); //可以存储null的key，放到第0个hash桶位置
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//这里面主要是如果hash一样，key一样，就把值换了，返回以前的value
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }


private V putForNullKey(V value) {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;//计算修改次数 
        addEntry(0, null, value, 0);//放到第0个位置 
        return null;
    }


 static int indexFor(int h, int length) {
        //这里主要是根据hash值算出在hash桶的index值，这个长度为什么要是2的n次方，因为它减一个1会把二进制码除了最高位全变为1，然后跟hash值&操作，算出来的值不会超过最大index
        return h & (length-1);
    }

void addEntry(int hash, K key, V value, int bucketIndex) {  //把数据放到Entry数组里面
        if ((size >= threshold) && (null != table[bucketIndex])) {//是否达到临界值进行扩容
            resize(2 * table.length);//两倍扩容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);//重新计算这个值需要放到的index位置
        }

        createEntry(hash, key, value, bucketIndex);
    }

 void createEntry(int hash, K key, V value, int bucketIndex) {//很简单就是放到数组里面去，这里的e指的是如果算出来的hash一样，那么index就会一样，然后就会把当前占位的挤到链表后面去，hash桶里面就放这个新值，然后这个原来的值就会加到这个新值的next位置进行关联
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

get代码主要是获取index位置的值，进行hash比较 == 比较 equle比较，如果一样就返回，如果不一样，就去找next，没找到就返回null

 public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }


 final Entry<K,V> getEntry(Object key) {
        if (size == 0) {
            return null;
        }

        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))//比较值
                return e;
        }
        return null;
    }

hash碰撞问题

hash碰撞是在使用key根据hash算法计算出index的时候会出现不同的key计算出index是一样的，这就是hash碰撞，jdk1.7中解决hash碰撞是使用了单链表的形式进行解决，计算出index一样，然后，去取值，把这个值挤到链表后面去，我们要尽可能的避免hash碰撞这种问题发生，因为在多线程的情况下会出现问题