• 如何存储数据 （put、get）

  
  

  • put数据

    
    
  [AppleScript] 纯文本查看 复制代码

  public V put(K key, V value) {
          if (table == EMPTY_TABLE) {
              inflateTable(threshold);
          }
          if (key == null)
              return putForNullKey(value);
          //计算key的hash值
          int hash = hash(key);
          //根据hash和数组的长度计算索引，即数组存放的位置
          int i = indexFor(hash, table.length);
          for (Entry<K,V> e = table[i]; e != null; e = e.next) {
              Object k;
              //如果值存在，则新值替换老值，并返回老值
              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                  V oldValue = e.value;
                  e.value = value;
                  e.recordAccess(this);
                  return oldValue;
              }
          }
          modCount++;
          //将算出的key的hash值，key，value ，以及索引存放在entry对象中，并加入table数组中
          addEntry(hash, key, value, i);
          return null;
      }

  • get数据

    
    
  [AppleScript] 纯文本查看 复制代码

  public V get(Object key) {
      //如果key为null，则返回null对于的value
      if (key == null)
          return getForNullKey();
      //根据key获取entry
      Entry<K,V> entry = getEntry(key);
      return null == entry ? null : entry.getValue();
  }
  final Entry<K,V> getEntry(Object key) {
      if (size == 0) {
          return null;
      }
      //计算出key的hash值
      int hash = (key == null) ? 0 : hash(key);
      //根据hash值获取索引，遍历索引下的所有的entry值
      for (Entry<K,V> e = table[indexFor(hash, table.length)];
           e != null;
           e = e.next) {
          Object k;
          //如果hash值相同并且key也相同则返回value
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      }
      return null;
  }

  • 默认容量为什么是16

    
    
  [AppleScript] 纯文本查看 复制代码

  //1前移4位 二进制1是 01 ，前移4位 则是 10000，即16
  static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

  我们先看一下源码如何获取index的值

  [AppleScript] 纯文本查看 复制代码

      static int indexFor(int h, int length) {
          // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
          //hash 值与 数组的长度-1进行位运算，长度必须是2的幂。
          return h & (length-1);
      }

  index的值是通过key的hash值与数组长度-1进行位运算来的。举个例子，

  • 计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001；

  • HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111

  • 把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9
    可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。

    
    

  ==长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。==

  • 负载因子为什么是0.75f

    
    
  /** * The load factor used when none specified in constructor. */static final float DEFAULT_LOAD_FACTOR = 0.75f;

  加载因子需要在时间和空间成本上寻求一种折衷。

  • 加载因子过高，例如为1，虽然减少了空间开销，提高了空间利用率，但同时也增加了查询时间成本

  • 加载因子过低，例如0.5，虽然可以减少查询时间成本，但是空间利用率很低，同时提高了rehash操作的次数。

    
    

  • hash冲突的产生与解决

    
    

  • 产生

    
    

  例如我们现在要加入一个key=A，value=a，先需要计算A的index，假如是2。那么结果如下：

  
  

  图1

  
  再加入一个key=A', value=a',此时刚好计算A'的index也是2，这时候就会产生冲突。

  
  

  • 解决hash冲突

    
    

  这个时候我们需要使用链表来解决hash冲突，当产生相同的index是，则通过Next指向同一个index的下一个节点，如图：
  (

  图二

  )
  注意：新来的Entry节点插入链表时，使用的是“头插法”。至于为什么不插入链表尾部，因为HashMap的作者发现后插入的Entry被查找的可能性更大

  
  

  • 什么时候会出现死锁

    
    

  当扩容时，需要将老的table的数据转移到新的table上，调用transfer发放进行转移。
  我们先看下transfer方法

  [AppleScript] 纯文本查看 复制代码

  void transfer(Entry[] newTable, boolean rehash) {
      int newCapacity = newTable.length;
      //循环遍历老的table
      for (Entry<K,V> e : table) {
          while(null != e) {
              Entry<K,V> next = e.next;
              //判断是否需要重新计算hash值
              if (rehash) {
                  e.hash = null == e.key ? 0 : hash(e.key);
              }
              int i = indexFor(e.hash, newCapacity);
              e.next = newTable[i];
              newTable[i] = e;
              e = next;
          }
      }
  }

  正常情况下，转移前链表顺序是1->2->3，逆序转移后新的t顺序变成 3->2->1，但是在多线程环境中，使用HashMap进行put操作时会引起死循环，导致死循环的原因是在多线程的情况下，会形成环形链表，这时是没有问题的，我们再看看get()方法中的获取Entry的方法

  [AppleScript] 纯文本查看 复制代码

  final Entry<K,V> getEntry(Object key) {
      if (size == 0) {
          return null;
      }
      int hash = (key == null) ? 0 : hash(key);
      for (Entry<K,V> e = table[indexFor(hash, table.length)];
           e != null;
           e = e.next) {
          Object k;
          if (e.hash == hash &&
              ((k = e.key) == key || (key != null && key.equals(k))))
              return e;
      }
      return null;
  }

  加入我们执行get方法找一个不存在的值的时候，for循环将会死循环，即会形成死锁

感谢分享