特点

• 线程不安全
• HashMap、和Hashtable、SynchronizedMap区别：
  • HashMap 线程不安全，可以有null的key值或value值。
  • hashtable 线程安全，不能有null的key值或value值。
  • ConcurrentHashMap 线程安全，不能有null的key值或value值。删除操作比较费时。
  • SynchronizedMap 线程安全，可以有null的key值或value值。
    • 可以通过Collections.synchronizedMap(new HashMap<String, Object>())方式创建
  • 性能:HashMap>ConcurrentHashMap>SynchronizedMap>Hashtable

构造方法

相关参数

• initialCapacity：初始最大容量，默认1<<4（2^4）,内部实际使用的变量是threshold(默认容量) ，实际最大容量并没有存放。
• loadFactor:加载因子(默认容量=初始最大容量*加载因子)，默认0.75
• threshold:默认容量，内部变量，根据initialCapacity生成。执行构造方法时，将输入的initialCapacity转为不小于当前数的最小的2^k的值，作为threshold。在第一次构建table时（第一次put(实际上时putVal方法)，执行resize()方法），table的大小设置为threshold，然后让threshold = threshold * loadFactor；后续每一次resize，都是table的大小 = table的大小 * 2；threshold = threshold * 2；
• 默认关系：threshold = initialCapacity * loadFactor(达到最大容量时不满足该等式)

平衡与折衷

• 加载因子：hash表中元素的填满程度，加载因子越大，空间利用率越高，冲突机会越高(查询成本越高)

代码解析

• public HashMap(int initialCapacity, float loadFactor)

public HashMap(int initialCapacity, float loadFactor) {        /**初始最大容量为非负整数*/        if (initialCapacity < 0)            throw new IllegalArgumentException("Illegal initial capacity: " +                                               initialCapacity);        /**        * static final int MAXIMUM_CAPACITY = 1 << 30;        * 当 initialCapacity 大于最大容量(2^30,约10.74亿)时,强制设置为容量为最大容量。        */        if (initialCapacity > MAXIMUM_CAPACITY)            initialCapacity = MAXIMUM_CAPACITY;        /**        * 加载因子为大于0的浮点数        * public static boolean isNaN(float v) {        *   return (v != v);        * }        * Float.isNaN(loadFactor):NaN（not-a-number），例如. float v = 0.0f/0.0f;        */        if (loadFactor <= 0 || Float.isNaN(loadFactor))            throw new IllegalArgumentException("Illegal load factor: " +                                               loadFactor);        /**赋值容量因子*/        this.loadFactor = loadFactor;        /**        * 转换输入的初始最大容量为2^k,赋值给threshold作为实际最大容量        * 这样做的意义待分析        */        this.threshold = tableSizeFor(initialCapacity);    }/*** 获取不小于当前数的最小的2^k的值.* 例如：31->32,65->128*/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;}

• public HashMap(int initialCapacity)

public HashMap(int initialCapacity) {    this(initialCapacity, DEFAULT_LOAD_FACTOR);}

• public HashMap()

/*** 在resize()方法中设置threshold的值* newCap = DEFAULT_INITIAL_CAPACITY;* newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);*/public HashMap() {    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

• public HashMap(Map<? extends K, ? extends V> m)
  • Map<String,Object> map = new HashMap<>(); Map.putAll(mapEntries);
    =>(完全等价于)
    Map<String,Object> map = new HashMap<>(mapEntries);
    （LinkedHashMap 继承于HashMap，该场景不一定完全等价，区别在于afterNodeInsertion方法，待梳理）

public HashMap(Map
     m) {    this.loadFactor = DEFAULT_LOAD_FACTOR;    putMapEntries(m, false);}public void putAll(Map
     m) {    putMapEntries(m, true);}final void putMapEntries(Map
     m, boolean evict) {    int s = m.size();    /**    * 当传入的map映射中存有对象时，进行插入逻辑    */    if (s > 0) {        /**        * table == null ，这时threshold = 0，需要进行设置threshold的值,tableSizeFor方法作用可见上文。        */        if (table == null) { // pre-size            float ft = ((float)s / loadFactor) + 1.0F;            int t = ((ft < (float)MAXIMUM_CAPACITY) ?                     (int)ft : MAXIMUM_CAPACITY);            if (t > threshold)                threshold = tableSizeFor(t);        }        /**        * 如果传入的映射中对象个数大于当前默认容量，容量扩大1倍        * (put方法中已经有resize逻辑，该操作的意义待分析)        */        else if (s > threshold)            resize();        /**        * 循环遍历每一个对象进行插入操作，和put方法完全一样        */        for (Map.Entry
     e : m.entrySet()) {            K key = e.getKey();            V value = e.getValue();            putVal(hash(key), key, value, false, evict);        }    }}

put

相关参数

• 暂未梳理

hashcode

• hashcode(Object)只和物理地址有关，和对象的内容没有关系。

class Student {    String name;    String[] likes;    public Student(String name){        this.name = name;    }    public Student(String name,String[] likes){        this.name = name;        this.likes = likes;    }}System.out.println(new Student("a").equals(new Student("a")));//falseStudent aa = new Student("a");System.out.println(aa.hashCode());//1410986873aa.name = "bcdefg";System.out.println(aa.hashCode());//1410986873aa.name = "a";System.out.println(aa.hashCode());//1410986873Student bb = new Student("a",new String[] {"爱好1","爱好2"});System.out.println(bb.hashCode());//2110245805bb.likes = new String[] {"爱好1","爱好4"};System.out.println(bb.hashCode());//2110245805HashMap
    
      hashMap2 = new HashMap
     
      (1 << 4);for(int i=0;i<13;i++) {    hashMap2.put(String.valueOf(i), 1);}System.out.println(hashMap2.hashCode());//5228HashMap
      
        hashMap3 = new HashMap
       
        (1 << 4);for(int i=0;i<13;i++) {    hashMap3.put(String.valueOf(i), 1);}System.out.println(hashMap3.hashCode());//5228System.out.println(((Object)hashMap2).equals(hashMap3));//true
       
      
     
    

• hashMap.hashcode对hashcode方法进行了重写，和key、value的hashcode有关系

public int hashCode() {    int h = 0;    Iterator
    
     
      > i = entrySet().iterator();    while (i.hasNext())        h += i.next().hashCode();    return h;}static class Node
      
        implements Map.Entry
       
         {    public final int hashCode() {        return Objects.hashCode(key) ^ Objects.hashCode(value);    }}public final class Objects {    public static int hashCode(Object o) {        return o != null ? o.hashCode() : 0;    }}public class Object {    /**    * 生成一个int类型的整型    * 1.同一个对象（未发生变化）只能生成一个hashcode，如果equals(Object的equals方法)，那么hashcode一定相等。    * 2.不同对象可能会生成一个hashcode    * 3.Object的hashCode方法只和物理地址有关，和对象的内容没有关系。    */    public native int hashCode();}
       
      
     
    

代码解析

• static final int hash(Object key)

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

• final Node<K,V>[] resize()

/*** 初始化或者给table容量加倍*/final Node
    
     [] resize() {    Node
     
      [] oldTab = table;    /**    * 旧的最大容量，初始化时为0    */    int oldCap = (oldTab == null) ? 0 : oldTab.length;    /**    * 旧的默认容量，一定有值。    */    int oldThr = threshold;    int newCap, newThr = 0;    /**非初始化执行操作*/    if (oldCap > 0) {        if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE;            return oldTab;        }        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                 oldCap >= DEFAULT_INITIAL_CAPACITY)             //非处初始化操作，oldCap>=16时，thr已经很规范了，直接二倍即可。            newThr = oldThr << 1; // double threshold    }    /**初始化执行的操作*/    else if (oldThr > 0) // initial capacity was placed in threshold        newCap = oldThr;    /**理论上永远也走不到该条件*/    else {               // zero initial threshold signifies using defaults        newCap = DEFAULT_INITIAL_CAPACITY;        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);    }    //初始化操作时newThr == 0,非处初始化操作，但oldCap<16时，通过cap和factor生成thr。    if (newThr == 0) {        float ft = (float)newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?                  (int)ft : Integer.MAX_VALUE);    }    /**    * 代码到这里的时候，结构已经扩增完成了，得到了最终的threshold和table结构    */    threshold = newThr;    @SuppressWarnings({"rawtypes","unchecked"})        Node
      
       [] newTab = (Node
       
        [])new Node[newCap];    table = newTab;    /**    * 将oldTab的值拷贝到newTab中    */    //table非null,性能优化    if (oldTab != null) {        for (int j = 0; j < oldCap; ++j) {            /**            * 为什么在for循环内new对象，是否性能更高？            */            Node
        
          e;            //内容非null,性能优化            if ((e = oldTab[j]) != null) {                oldTab[j] = null;                if (e.next == null)                    //通过e的hash值和当前最大容量来确定一个唯一的hash值？简单推测                    newTab[e.hash & (newCap - 1)] = e;                else if (e instanceof TreeNode)                    //红黑树？待梳理                    ((TreeNode
         
          )e).split(this, newTab, j, oldCap); else { // preserve orde //对链表结构的处理 //低位组low Node
          
            loHead = null, loTail = null; //高位组high Node
           
             hiHead = null, hiTail = null; Node
            
              next; do { next = e.next; /** * key为null,e.hash=0 * 初始化时oldcap = 0 */ if ((e.hash & oldCap) == 0) { //第一次进入 if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { //第一次进入 if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //存在低位组的对象 if (loTail != null) { //去掉无效的值，防止重复计算高位对象 loTail.next = null; newTab[j] = loHead; } //存在高位组的对象 if (hiTail != null) { //去掉无效的值，防止重复计算低位对象 hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab;}
            
           
          
         
        
       
      
     
    

• public V put(K key, V value)

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
    
     [] tab; Node
     
       p; int n, i;    if ((tab = table) == null || (n = tab.length) == 0)        n = (tab = resize()).length;    if ((p = tab[i = (n - 1) & hash]) == null)        tab[i] = newNode(hash, key, value, null);    else {        Node
      
        e; K k;        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k))))            e = p;        else if (p instanceof TreeNode)            e = ((TreeNode
       
        )p).putTreeVal(this, tab, hash, key, value);        else {            for (int binCount = 0; ; ++binCount) {                if ((e = p.next) == null) {                    p.next = newNode(hash, key, value, null);                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                if (e.hash == hash &&                    ((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }        if (e != null) { // existing mapping for key            V oldValue = e.value;            if (!onlyIfAbsent || oldValue == null)                e.value = value;            afterNodeAccess(e);            return oldValue;        }    }    ++modCount;    if (++size > threshold)        resize();    afterNodeInsertion(evict);    return null;}
       
      
     
    

小结：

• java位运算相关知识待归纳。 (位运算的目的是提高效率)
  • 1 << k(2^k)
  • ^是异或运算符，异或的规则是转换成二进制比较，相同为0，不同为1.
  • int c=a ^ b ; a=c ^ b;b=c ^ a;
  • a&b 的操作的结果：a、b中对应位同时为1，则对应结果位也为1
• double和float区别待归纳。
• LinkedHashMap、HashMap、treemap、treenodes关系
• 为什么n初始化构造map时，转换输入的初始最大容量为2^k,赋值给threshold作为实际最大容量。