HashMap 的正确初始化姿势以及并发问题(jdk1.7)

本贴最后更新于 586 天前,其中的信息可能已经时移世改

初始化

    // 假设我们要存放1000个元素
    Map map = new HashMap(1000);
    for(int i = 0; i < 1000; i++) {
        map.put(i, null);
    }
    // 在初始化Map时,hashmap会计算出table大小应该为1024,但是1024*0.75 = 768
    // 也就是说在put第768个时就会触发扩容,导致rehash
    // 所以我们应该使用 Map map = new HashMap((int)(1000 / 0.75) + 1);
    // 这样初始化时table的大小为2048,2048*0.75>1000,所以我们把1000个元素都put进去也不会触发rehash
    // 初始化HashMap对象时,并没有初始化table
    public HashMap(int initialCapacity, float loadFactor) {
        ......
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
  
    // 第一次put数据时,table为null,调用resize()
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        ......
    }
  
    // resize函数中,初始化了table,并且修改了threshold的值为 newCap * loadFactor
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        ......
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        ......
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        ......
    }

多线程 put 时导致成环

在 jdk1.7 及之前的版本中,解决 hash 冲突使用的方式是插入链表,并且是头插法,头插法的代码下面有

hash 桶的头结点是真实的节点,不是哑结点

头插法

public class Foo {
    public static void main(String[] args) {
        Node[] table = new Node[5];
        int index = 2;

        Node node = new Node("a");
        node.next = table[index];
        table[index] = node;

        Node b = new Node("b");
        b.next = table[index];
        table[index] = b;

        Node c = new Node("c");
        c.next = table[index];
        table[index] = c;
        System.out.println(table[index]);
        // 输出结果为: c->b->a->
    }

    static class Node{
        private String value;
        private Node next;

        Node(String value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return value + " ->" + (next != null ? next.toString() : "");
        }
    }
}
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3012 引用 • 8158 回帖 • 548 关注
  • 代码
    447 引用 • 545 回帖 • 6 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...