您的位置: 首页  >  文章  >  HashMap实现原理总结

HashMap实现原理总结

分类: 文章 • 2022-10-23 11:36:01

hashmap初始化一定是2的倍数原因

比如：
默认数组大小是16时，他的二进制码为：0001 0000
HashMap实现原理总结
计算下表的时候将length-1，进行与运算，与运算比取模运算效率高，-1之后的二进制为：0000 1111
这样刚好数组下标的取值范围为：0~15

h 0001 1001
& 0000 1111

解决hash冲突的办法

  • 链表法
    这是jdk7主要的对同一hash值处理的方法，jdk8增加红黑树结构
  • 再hash法
    使得每个hash值都参与运算，使其分布的更均匀
    HashMap实现原理总结

jdk7与jdk8插入顺序

  • jdk7从头部插入，即新元素占用table的位置，并将next指向之前的元素
    HashMap实现原理总结
  • jdk8因为要循环链表长度，大于8采用红黑树，"顺便"将元素放到尾节点：
    HashMap实现原理总结

jdk7与jdk8扩容

  • jdk7的扩容条件：总数量大于阈值容量并且加入的哪个table里面的元素不能为空，最后重新计算下标到新的数组；
    HashMap实现原理总结
    这个是阈值容量的计算，capacity默认2的30次方，loadFactor默认0.75
    HashMap实现原理总结
    最后会刷新阈值容量
    HashMap实现原理总结
    jdk8因为有红黑树的结构，对扩容条件进行的宽松处理，只需大于阈值容量，
    HashMap实现原理总结
  • 新数据的从新分配优化(扩容前大小假如为16)
    扩容前数组下标计算:
    例子(1)
    扩容前：
    h 0000 0101
    & 0000 1111
    扩容后：
    h 0000 0101
    & 0001 1111
    例子(2)
    扩容前：
    h 0001 0101
    & 0000 1111
    扩容后：
    h 0001 0101
    & 0001 1111
    从上面例子看出如果数据的hash值为 0000 0101 扩容前后的数组下标并无差异，但数据0001 0101 的时候数据就不同，所以这里如果数据是类似0001 0101 的话，刚好平移的是原先数组的长度，这也是解决死锁的一个办法。
    jdk7扩容时头插法死锁的问题分析：http://www.importnew.com/22011.html
    HashMap实现原理总结

线程不安全的处理（fast-fail）

模拟报错代码：

Map<Integer, Integer> map = new HashMap<>();
map.put(1, 1);
map.put(2, 2);
Iterator<Integer> iterator = map.keySet().iterator();
while (iterator.hasNext()) {
    Integer key = iterator.next();
        System.out.println(key);
        map.remove(key);
       //正确应该这样使用： iterator.remove();
}

遍历之前执行expectedModCount = modCount;而modCount每一次修改都会++的操作，遍历的时候如果修改的操作跟遍历之前的不一样了，说明遍历的过程中被修改了，给出报错，也就是快速失败。
HashMap实现原理总结
remove()方法(这个才是安全的方法)
HashMap实现原理总结
remove(key)方法：
这里只会进行++modeCount的操作，所以下次遍历的时候会报错
HashMap实现原理总结

最后实现一个简单的hashmap加深理解

/**
 * @Auther: 郭敬仰
 * @Date: 2019/1/24 12:44
 * @Description:
 */
public class MyHashMap<K, V> {
    private static Integer CAPACITRY = 8;
    private Entry[] table;
    private int size;

    public MyHashMap() {
        this.table = new Entry[CAPACITRY];
    }

    public int size() {
        return size;
    }

    public Object get(Object key) {
        int hash = key.hashCode();
        int i = hash % CAPACITRY;

        for (Entry<K, V> entry = table[i]; entry != null; entry = entry.next) {
            if (entry.k.equals(key)) {
                return entry.v;
            }
        }
        return null;
    }

    public V put(K key, V value) {
        int hash = key.hashCode();
        int i = hash % CAPACITRY;

        for (Entry<K, V> entry = table[i]; entry != null; entry = entry.next) {
            if (entry.k.equals(key)) {
                V oldValue = entry.v;
                entry.v = value;
                return oldValue;
            }
        }
        addEntry(key, value, i);
        return null;
    }

    private void addEntry(K key, V value, int i) {
        Entry entry = new Entry(key, value, table[i]);
        table[i] = entry;
        size++;
    }


    class Entry<K, V> {
        private K k;
        private V v;
        private Entry next;

        public Entry(K k, V v, Entry next) {
            this.k = k;
            this.v = v;
            this.next = next;
        }

        public K getK() {
            return k;
        }

        public void setK(K k) {
            this.k = k;
        }

        public V getV() {
            return v;
        }

        public void setV(V v) {
            this.v = v;
        }

        public Entry getNext() {
            return next;
        }

        public void setNext(Entry next) {
            this.next = next;
        }
    }

    public static void main(String[] args) {
        MyHashMap<String, String> map = new MyHashMap<String, String>();
        for (int i = 1; i < 20; i++) {
            map.put("hehe" + i, i + "");
        }
    }
}

其它相关博客推荐阅读：
https://blog.****.net/xuehuagongzi000/article/details/71449179
http://www.importnew.com/23164.html
https://www.cnblogs.com/chengxiao/p/6059914.html#t2

相关推荐