JavaHashMap分析之三：放入元素

现在，有了hash code,来考虑如何计算放入数组的位置。hash code值通常会很大，但是数组的大小有限，默认只有16，大的也不能超过2的30次方。所以，用模运算来保证在数组大小范围内是合理的，比如:index = hash code % array size.不过这有点慢，JDK采用了更快的算法。这个更快的算法源于一个数学规律，就是如果size是2的N次方，那么数X对size的模运算结果等价于X和size-1的按位与运算，也就是 X % size <=> X & (size -1).按位与只消耗一个CPU周期，当然快多了。现在就可理解为什么要故意把数组大小弄成2的N次方了。再回头看一开始计算数组大小的代码，完全理解了。

创新互联建站专注为客户提供全方位的互联网综合服务，包含不限于网站制作、成都网站设计、达日网络推广、微信小程序开发、达日网络营销、达日企业策划、达日品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联建站为所有大学生创业者提供达日建站搭建服务，24小时服务热线：028-86922220，官方网址：www.cdcxhl.com

 
 
 
  
  
  int capacity = 1;  
  
  
          while (capacity < initialCapacity)  
  
  
              capacity <<= 1;

比如size=16，二进制表示如下：（32位）

0000000000000000000000000010000

size-1=15，表示如下：

0000000000000000000000000001111

假如hash code=4

0000000000000000000000000000100

4 & 15 结果为：

0000000000000000000000000000100

假如hash code=6

0000000000000000000000000000101

6 & 15 结果为：

0000000000000000000000000000101

假如hash code=38

0000000000000000000000000100110

38 & 15 结果为：

0000000000000000000000000000110

通过观察这三个例子，又可以发现一个特点，也就是X & size-1 的结果受到了size的阶数的限制，这里size=16,阶数为4.结果就是只用低4位的1和X按位与，而X的高位没有用到。这会导致重复率相当高。如果用一个算法将X的低位重新计算，比如根据所有位的值进行重新计算，就可以使得hash值分布更均匀。下面的代码揭示了在真正按位与之前，调用了hash函数，进行了一堆位运算。至于为什么用这个算法，我也不知道其来历。

 
 
 
  
  
  public V put(K key, V value) {  
  
  
          if (key == null)  
  
  
              return putForNullKey(value);  
  
  
          int hash = hash(key.hashCode());  
  
  
          int i = indexFor(hash, table.length);  
  
  
          for (Entry 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++;  
  
  
          addEntry(hash, key, value, i);  
  
  
          return null;  
  
  
      }  
  
  
   
  
  
      static int hash(int h) {  
  
  
          // This function ensures that hashCodes that differ only by  
  
  
          // constant multiples at each bit position have a bounded  
  
  
          // number of collisions (approximately 8 at default load factor).  
  
  
          h ^= (h >>> 20) ^ (h >>> 12);  
  
  
          return h ^ (h >>> 7) ^ (h >>> 4);  
  
  
      }  
  
  
   
  
  
      static int indexFor(int h, int length) {  
  
  
          return h & (length-1);  
  
  
      }  
  
  
   
  
  
      void addEntry(int hash, K key, V value, int bucketIndex) {  
  
  
          Entry e = table[bucketIndex];  
  
  
          table[bucketIndex] = new Entry(hash, key, value, e);  
  
  
          if (size++ >= threshold)  
  
  
              resize(2 * table.length);  
  
  
      }

上面的for循环是查找并替换符合条件的对象，如果找不到，则添加新的对象。查找到的条件（必须都满足）是：

1.hash值相等

2.key的引用相同或者key的值相等。

名称栏目：JavaHashMap分析之三：放入元素
链接分享：http://www.hantingmc.com/qtweb/news15/278865.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容