hashmap学习

1.数据结构

数组+链表的形式    【】【】【】【】【】

                                     |       |       |       |       |

                                  【】【】【】【】【】

数组长度：固定，即初始化HashMap时的capacity。当需要数组长度时，会rehash，重新计算容器中所有值的位置

链表长度：可以扩展，即冲突的对象放入链表中

 

2.如何从map中寻找值

    public V get(Object key) {
        Object k = maskNull(key);
        int hash = hash(k);
        int i = indexFor(hash, table.length);
        Entry<K,V> e = table[i]; 
        while (true) {
            if (e == null)
                return null;
            if (e.hash == hash && eq(k, e.key)) 
                return e.value;
            e = e.next;
        }
    }

    static int hash(Object x) {
        int h = x.hashCode();

        h += ~(h << 9);
        h ^=  (h >>> 14);
        h +=  (h << 4);
        h ^=  (h >>> 10);
        return h;
    }

    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 

 a.计算hash值（计算hash值，采用这种旋转Hash函数的主要目的是让原有hashCode的高位信息也能被充分利用，且兼顾计算效率以及数据统计的特性）

 b.通过hash值和capcity作位运算，获取数组中的index

 c.在指定数组元素中，用equals索引链表，获得查询的值

 

 

3.几个变量

initialCapacity：初始化map中元素的个数的参数，不代表是最好map中最后设置的值

loadFactor：负载因子

capacity：Find a power of 2 >= initialCapacity，实际容量

threshold：capacity*loadFactor=threshold，当map中元素的数据>threshold时，capacity会double，然后会做最耗性能的resize

 

4.initialCapacity的参数值，一定要根据业务估算，否则可能会rehash，浪费性能

 

5.为何将capacity设为2的N次方？

因为java可以利用位运算作取模运算，提供运行速度

 

6.非线程安全的Map VS Collections.synchronizedMap

fail-fast机制（比如，循环遍历时，不能添加或者删除map中元素）

 

7.linkedHashMap VS LRU(最近最久未使用算法)

a.实现方式：HashMap的子类，利用双链表维持内部元素的关系

b.内部header、before、after3个指针引用

c.由于增加了维护链接列表的开支，其性能要比 HashMap 稍逊一筹，不过有一点例外：LinkedHashMap的迭代所需时间与其的所包含的元素成比例；而HashMap 迭代时间很可能开支较大，因为它所需要的时间与其容量（分配给Key空间的长度）成比例。一言以蔽之，随机存取用HashMap，顺序存取或是遍历用 LinkedHashMap。

d.缺省情况下，LinkedHashMap采取的更新策略是类似于队列的FIFO，如果你想实现更复杂的更新逻辑比如LRU（最近最少使用）等，将removeEldestEntry与accessOrder一起使用，就可以实现最基本的内存缓存。如果accessOrder被设置为true，则每次访问元素时，都将该元素移至head的前面，即链表的尾部。

 

8.WeakHashMap

a.强引用、软引用、弱引用、虚幻引用

b.WeakHashMap采用的策略是，只要作为key的对象已经不存在了（超出生命周期），就不会阻止垃圾收集器清空此条目，即使当前机器的内存并不紧张。