浅谈HashMap

HashMap结构图

image.png

HashMap主要方法

• final int hash(Object k)
• static int indexFor(int h, int length)
• void resize(int newCapacity)
• public V put(K key, V value)
• public V get(Object key)
• public V remove(Object key)

HashMap方法解读

final int hash(Object k)源码：

 final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

这段代码的含义我确实搞不清楚，简单理解的话就是做一次hash算法

static int indexFor(int h, int length)源码：

//做一次&运算，定位到在数组的位置
 static int indexFor(int h, int length) {
        return h & (length-1);
    }

public V get(Object key)的源码：

public V get(Object key) {
        //如果这个key为null就会放入数组的第0个位置
        if (key == null)
            return getForNullKey();
        //获取key为非0的元素
        Entry<K,V> entry = getEntry(key);
        return null == entry ? null : entry.getValue();
    }
//获取key为0的元素，因为数组第0个位置是一个链表组成，遍历这个链表就可以找到对应的值
 private V getForNullKey() {
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }
//当key不为0的时候
final Entry<K,V> getEntry(Object key) {
        //这就是之前的hash算法，算出对应的hash值
        int hash = (key == null) ? 0 : hash(key);
        //indexFor这也就是前面讲的找到数组对应的位置
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            //判断是否是这个key对应的数据条件是：hash值相等&对应的key值相等，或者key equals
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

总结起来就是：
如果这个key为null就走null的获取方式：其实就是对数据第0个位置的链表进行遍历。
如果这个key不为null就走不为null的获取方式：首先，计算出hash值，然后，定位到在数组的位置，最后遍历这个链表，条件就是hash值相等并且key相等或者equals

public V remove(Object key) 源码为：

public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
//真正的删除元素
final Entry<K,V> removeEntryForKey(Object key) {
        //算hash值
        int hash = (key == null) ? 0 : hash(key);
       //定位位置
        int i = indexFor(hash, table.length);
        // 将table[i]赋值给prev
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;
        //开始遍历删除
        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            //判断相等条件
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
              //如果删除的元素为第一个，那么下一个元素作为第一个
                if (prev == e)
                    table[i] = next;
                else
                     //删除当前元素，把当前元素的前一个节点指向当前元素的后一个节点
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            //依次循环查找
            prev = e;
            e = next;
        }
        return e;
    }

总结起来就是：
第一步：算出hash；第二步：定位位置；第三步：遍历定位位置的链表，找到对应元素删除。

public V put(K key, V value)源码为：

 public V put(K key, V value) {
        // key为null时的put
        if (key == null)
            return putForNullKey(value);
        //hash
        int hash = hash(key);
        //index
        int i = indexFor(hash, table.length);
        //如果是index位置对应的链表里面有想要put的元素，用新的元素覆盖老的元素，**说明hashmap如果key相同的话，value会相互覆盖**
        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))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //如果这个key没有的话，新增一个entry
        addEntry(hash, key, value, i);
        return null;
    }
//新增操作
void addEntry(int hash, K key, V value, int bucketIndex) {
        //计算需要不需要扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
             //扩容操作
             resize(2 * table.length);
            //重新hash
            hash = (null != key) ? hash(key) : 0;
            //重新index
            bucketIndex = indexFor(hash, table.length);
        }
        //新增entry
        createEntry(hash, key, value, bucketIndex);
    }
//新增entry
void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }
//这个一个头插法，新来的元素插入头部
 Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
//扩容操作
void resize(int newCapacity) {
        //扩容操作之前的一些判断处理，还有一些我也不足道什么意思，不过不是很重要，我们主要看一下transfer
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry[] newTable = new Entry[newCapacity];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }
//把原来的元素复制到新的数组里
void transfer(Entry[] newTable, boolean rehash) {
        //创建一个新的数组
        int newCapacity = newTable.length;
      //循环老的数组
        for (Entry<K,V> e : table) {
            //遍历每一个数组对应的链表
            while(null != e) {
                Entry<K,V> next = e.next;
                //hash
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                // index
                int i = indexFor(e.hash, newCapacity);
                //这一点比较bug,不是很好理解，我会贴一篇比较清楚的文章
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

put操作总结起来就是：
第一：hash,index之后找原来的链表查看是否存在，存在的话覆盖掉
第二：不存在就新建一个entry，新建的前提需要考虑容量是否超过阈值，没有超过直接新建
第三：超过阈值，就需要扩容2*size,还需要把原来的table里面的元素复制到新的table里，这里需要注意如果是多线程环境操作的话可能形成环状结构导致CPU飙升
第四：新增entry是才有头插法，好处是不用遍历。
这里我必须贴出一遍写的很精彩的文章，还有他对resize的详细介绍：
hashmap扩容机制

HashMap遍历方式

目前我常用的就是这个了，还有其他的欢迎补充。

for (Map.Entry<String, String> entry : map.entrySet()) {
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }

HashMap其他特性介绍

• hashmap的组成结构为数组+链表。
• hashmap是非线程安全的，在多线程的环境下是会出问题的。
• hashmap 的key可以为空，value也可以为空。
• hashmap的默认数组长度为16，默认加载因子为0.75f，当阈值的时候是会扩容的，在扩容的时候需要注意在多线程的环境里有可能出现环形。