HashMap 大全

to be man know hashmap most

hashmap里面的数学知识《链表到红黑树转化的阈值为啥是 8》

我看到了泊松分布

* Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:

1） 查找性能和存储之间的一个折中，有理有据，细节拉满。

2） 为啥是红黑树？ 而不是平衡树
红黑树，在包含 插入，删除，查询操作的时候，性能要好于avl。
avl 是严格的二叉查找， 对于删除，修改会有很多的 rebalance炒作，当然查询更快。
rb-tree 是一个综合的性能折中。
红黑树的模型，需要另外的篇幅： 通过 好几个约束条件来保证， 黑色节点的平衡，
从而不完美的平衡，有比较不错的查询速度。
- 黑色根节点
- 红色节点子节点都是黑色
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

尽可能想要分散的hash函数

这个要从 后面的寻址说起，
hash &（length-1）
length 的长度通常不会很长，比如16位的话，那么hash 值，如果超过16位呢？ 那么高位的数值就会丢失
就有可能造成，相对不均匀。例如：最极端的情况，就是一大堆 hash，就高位不一样，然后低位全部一样，
这个寻址后，就会造成分散不均匀。
hashmap在设计的时候，有很多这样的优化考虑。
所以，给定一个 key， 他并没有只用 key.hashCode.
还做了一定的操作

static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

原理就是把hashcode与本身右移动16位之后，做一个与或，把高位16位的一些数值与低位16位搅合一下。

为啥size 都是2的 N次方。

1）利用到一个数学公司，当 len = 2^n次方的时候
hash% len = hash &(len-1).
要知道， 位运算的性能比 取莫要快很多。
2） 在hashmap resize 的时候， 保持这个特型的话，
可以让现有的元素非常快速的计算出 resize 之后的坐标，无需重新计算hash，也无需处理冲突。
一切都可以平移。
power-of-two masking，这个原理可以好好看看。

多线程相关 （1）【fail fast】

   abstract class HashIterator {
        Node<K,V> next;        // next entry to return
        Node<K,V> current;     // current entry
        int expectedModCount;  // for fast-fail
        int index;             // current slot

        HashIterator() {
            expectedModCount = modCount;
           *// 构造iterator 的时候，就设置了一个 snapshot下的 modCount *
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // advance to first entry
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {
            return next != null;
        }

        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                **调用 next 的时候都会检查 modCount是否已经修改，否则抛出异常**
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
           **如果使用自己的remove方法，会更新这个值，就不会抛出 mdfe**
            expectedModCount = modCount;
        }
    }

对于hashmap的foreach，以及key，value 等list 的foreach，都实现了fail-fast机制。

多线程相关（2） hashmap 为啥不是线性安全的？

https://www.cnblogs.com/developer_chan/p/10450908.html
HashMap是线程不安全的，其主要体现：
1.在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
扩容的时候采用链表头插法
2.在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。

concurrentMap

1） 1.7 和1.8 的区别，各自的优劣
2） 为什么不用segment
3） cas的场景，synchronized 和 reenterlock 的却别和优劣
4） CounterCell @sun.misc.Contended 高级特型的作用