HashMap的设计原理和实现分析

转自: http://blog.csdn.net/luanlouis/article/details/41576373?utm_source=tuicool&utm_medium=referral

 

HashMap在Java开发中有着非常重要的角色地位,每一个Java程序员都应该了解HashMap。

    本文主要从源码角度来解析HashMap的设计思路,并且详细地阐述HashMap中的几个概念,并深入探讨HashMap的内部结构和实现细节,讨论HashMap的性能问题,并且在文中贯穿着一些关于HashMap常见问题的讨论。     

 

读完本文,你会了解到:     1. HashMap的设计思路和内部结构组成

         2. HashMap中的一些概念: 什么是阀值?为什么会有阀值?什么是加载因子?它们有什么作用?

         3. HashMap的性能问题以及使用事项

         4. HashMap的源码实现解析

         5. 为什么JDK建议我们重写Object.equals(Object obj)方法时,需要保证对象可以返回相同的hashcode值?


 

1. HashMap设计思路以及内部结构组成

 

HashMap设计思路

     Map<K,V>是一种以键值对存储数据的容器,而HashMap则是借助了键值Keyhashcode值来组织存储,使得可以非常快速和高效地地根据键值key进行数据的存取。

     对于键值对<Key,Value>HashMap内部会将其封装成一个对应的Entry<Key,Value>对象,即Entry<Key,Value>对象是键值对<Key,Value>的组织形式;

     对于每个对象而言,JVM都会为其生成一个hashcode值。HashMap在存储键值对Entry<Key,Value>的时候,会根据Keyhashcode值,以某种映射关系,决定应当将这对键值对Entry<Key,Value>存储在HashMap中的什么位置上;

     当通过Key值取数据的时候,然后根据Key值的hashcode,以及内部映射条件,直接定位到Key对应的Value值存放在什么位置,可以非常高效地将Value值取出。

     

为了实现上述的设计思路,在HashMap内部,采用了数组+链表的形式来组织键值对Entry<Key,Value>

HashMap内部维护了一个Entry[] table 数组,当我们使用 new HashMap()创建一个HashMap时,Entry[] table 的默认长度为16。Entry[] table的长度又被称为这个HashMap容量(capacity

对于Entry[] table的每一个元素而言,或为null,或为由若干个Entry<Key,Value>组成的链表。HashMap中Entry<Key,Value>的数目被称为HashMap大小(size);

Entry[] table中的某一个元素及其对应的Entry<Key,Value>又被称为桶(bucket);     

其结构如下图所示:

    HashMap内部组织结构由上图所示,现在来看一下HashMap的基本工作流程:

2. 什么是阀值?为什么会有阀值?什么是加载因子?它们有什么作用?

 

        HashMap设计的初衷,是为了尽可能地迅速根据KeyhashCode值, 直接就可以定位到对应的Entry<Key,Value>对象,然后得到Value

      请读者考虑这样一个问题:

      当我们使用 HashMap map = new HashMap()语句时,我们会创建一个HashMap对象,它内部的 Entry[] table的大小为 16,我们假定Entry[] table的大小会改变。现在,我们现在向它添加160Key值完全不同的键值对<Key,Value>,那么,该HashMap内部有可能下面这种情况:即对于每一个桶中的由Entry<Key,Value>组成的链表的长度会非常地长!我们知道,对于查找链表操作的时间复杂度是很高的,为O(n)。这样的一个HashMap的性能会很低很低,如下图所示:

现在再来分析一下这个问题,当前的HashMap能够实现:

     1. 根据KeyhashCode,可以直接定位到存储这个Entry<Key,Value>的桶所在的位置,这个时间的复杂度为O(1);

     2. 在桶中查找对应的Entry<Key,Value>对象节点,需要遍历这个桶的Entry<Key,Value>链表,时间复杂度为O(n);

   那么,现在,我们应该尽可能地将第2个问题的时间复杂度o(n)降到最低,读者现在是不是有想法了:我们应该要求桶中的链表的长度越短越好!桶中链表的长度越短,所消耗的查找时间就越低,最好就是一个桶中就一个Entry<Key,Value>对象节点就好了!

     这样一来,桶中的Entry<Key,Value>对象节点要求尽可能第少,这就要求,HashMap中的桶的数量要多了。

     我们知道,HashMap的桶数目,即Entry[] table数组的长度,由于数组是内存中连续的存储单元,它的空间代价是很大的,但是它的随机存取的速度是Java集合中最快的。我们增大桶的数量,而减少Entry<Key,Value>链表的长度,来提高从HashMap中读取数据的速度。这是典型的拿空间换时间的策略。

      但是我们不能刚开始就给HashMap分配过多的桶(即Entry[] table 数组起始不能太大),这是因为数组是连续的内存空间,它的创建代价很大,况且我们不能确定给HashMap分配这么大的空间,它实际到底能够用多少,为了解决这一个问题,HashMap采用了根据实际的情况,动态地分配桶的数量。

     

HashMap的权衡策略

   要动态分配桶的数量,这就要求要有一个权衡的策略了,HashMap的权衡策略是这样的:

             如果

                         HashMap的大小> HashMap的容量(即Entry[] table的大小)*加载因子(经验值0.75)

               

                         HashMap中的Entry[] table 的容量扩充为当前的一倍;

                        然后重新将以前桶中的Entry<Key,Value>链表重新分配到各个桶中

 

上述的  HashMap的容量(即Entry[] table的大小) * 加载因子(经验值0.75)就是所谓的阀值(threshold)

                 

 

            最后,请读者看一个实例:

             默认创建的HashMap map =new HashMap();map的容量是 16,那么,当我们往 map中添加第几个完全不同的键值对<Key,Value>时,HashMap的容量会扩充呢? 

          呵呵,很简单的计算:由于默认的加载因子是0.75 ,那么,此时map的阀值是 16*0.75 = 12,即添加第13 个键值对<Key,Value>的时候,map的容量会扩充一倍。

            这时候读者可能会有疑问:本来Entry[] table的容量是16,当放入12个键值对<Key,Value>后,不是至少还剩下4个Entry[] table 元素没有被使用到吗?这不是浪费了宝贵的空间了吗?!   确实如此,但是为了尽可能第减少桶中的Entry<Key,Value>链表的长度,以提高HashMap的存取性能,确定的这个经验值。如果读者你对存取效率要求的不是太高,想省点空间的话,你可以new HashMap(int initialCapacity, float loadFactor)构造方法将这个因子设置得大一些也无妨。

    

2. HashMap的算法实现解析

       HashMap的算法实现最重要的两个是put() 和get() 两个方法,下面我将分析这两个方法:

[java] view plain copy
 
 print?
  1. public V put(K key, V value);  
  2. public V get(Object key);   

     另外,HashMap支持Key值为null 的情况,我也将详细地讨论这个问题。

    1. 向HashMap中存储一对键值对<Key,Value>流程---put()方法实现:

put()方法-向HashMap存储键值对<Key,Value>

 

a.  获取这个Key的hashcode值,根据此值确定应该将这一对键值对存放在哪一个桶中,即确定要存放桶的索引;

b.  遍历所在桶中的Entry<Key,Value>链表,查找其中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,

c1. 若已存在,定位到对应的Entry<Key,Value>,其中的Value值更新为新的Value值;返回旧值;

c2. 若不存在,则根据键值对<Key,Value> 创建一个新的Entry<Key,Value>对象,然后添加到这个桶的Entry<Key,Value>链表的头部。

d.  当前的HashMap的大小(即Entry<key,Value>节点的数目)是否超过了阀值,若超过了阀值(threshold),则增大HashMap的容量(即Entry[] table 的大小),并且重新组织内部各个Entry<Key,Value>排列。

详细流程如下列的代码所示:
[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * 将<Key,Value>键值对存到HashMap中,如果Key在HashMap中已经存在,那么最终返回被替换掉的Value值。 
  3.  * Key 和Value允许为空 
  4.  */  
  5. public V put(K key, V value) {  
  6.       
  7.     //1.如果key为null,那么将此value放置到table[0],即第一个桶中  
  8.     if (key == null)  
  9.         return putForNullKey(value);  
  10.     //2.重新计算hashcode值,  
  11.     int hash = hash(key.hashCode());  
  12.     //3.计算当前hashcode值应当被分配到哪一个桶中,获取桶的索引  
  13.     int i = indexFor(hash, table.length);  
  14.     //4.循环遍历该桶中的Entry列表  
  15.     for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  16.         Object k;  
  17.         //5. 查找Entry<Key,Value>链表中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,  
  18.         //已经存在,则将Value值覆盖到对应的Entry<Key,Value>对象节点上  
  19.         if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//请读者注意这个判定条件,非常重要!!!  
  20.             V oldValue = e.value;  
  21.             e.value = value;  
  22.             e.recordAccess(this);  
  23.             return oldValue;  
  24.         }  
  25.     }  
  26.     modCount++;  
  27.     //6不存在,则根据键值对<Key,Value> 创建一个新的Entry<Key,Value>对象,然后添加到这个桶的Entry<Key,Value>链表的头部。  
  28.     addEntry(hash, key, value, i);  
  29.     return null;  
  30. }  
  31.   
  32. /** 
  33.  * Key 为null,则将Entry<null,Value>放置到第一桶table[0]中 
  34.  */  
  35. private V putForNullKey(V value) {  
  36.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
  37.         if (e.key == null) {  
  38.             V oldValue = e.value;  
  39.             e.value = value;  
  40.             e.recordAccess(this);  
  41.             return oldValue;  
  42.         }  
  43.     }  
  44.     modCount++;  
  45.     addEntry(0null, value, 0);  
  46.     return null;  
  47. }  

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * 根据特定的hashcode 重新计算hash值, 
  3.  * 由于JVM生成的的hashcode的低字节(lower bits)冲突概率大,(JDK只是这么一说,至于为什么我也不清楚) 
  4.  * 为了提高性能,HashMap对Key的hashcode再加工,取Key的hashcode的高字节参与运算 
  5.  */  
  6. static int hash(int h) {  
  7.     // This function ensures that hashCodes that differ only by  
  8.     // constant multiples at each bit position have a bounded  
  9.     // number of collisions (approximately 8 at default load factor).  
  10.     h ^= (h >>> 20) ^ (h >>> 12);  
  11.     return h ^ (h >>> 7) ^ (h >>> 4);  
  12. }  
  13.   
  14. /** 
  15.  * 返回此hashcode应当分配到的桶的索引 
  16.  */  
  17. static int indexFor(int h, int length) {  
  18.     return h & (length-1);  
  19. }  

 

 

 

当HashMap的大小大于阀值时,HashMap容量的扩充算法 当当前的HashMap的大小大于阀值时,HashMap会对此HashMap的容量进行扩充,即对内部的Entry[] table 数组进行扩充。
HashMap对容量(Entry[] table数组长度) 有两点要求:
1. 容量的大小应当是 2的N次幂;
2. 当容量大小超过阀值时,容量扩充为当前的一倍;

这里第2点很重要,如果当前的HashMap的容量为16,需要扩充时,容量就要变成16*2 = 32,接着就是32*2=64、64*2=128、128*2=256.........可以看出,容量扩充的大小是呈指数级的级别递增的。

    这里容量扩充的操作可以分为以下几个步骤:

       1. 申请一个新的、大小为当前容量两倍的数组;

     2.  将旧数组的Entry[] table中的链表重新计算hash值,然后重新均匀地放置到新的扩充数组中;

     3.  释放旧的数组

由上述的容量扩充的步骤来看,一次容量扩充的代价非常大,所以在容量扩充时,扩充的比例为当前的一倍,这样做是尽量减少容量扩充的次数。

为了提高HashMap的性能:

               1.在使用HashMap的过程中,你比较明确它要容纳多少Entry<Key,Value>,你应该在创建HashMap的时候直接指定它的容量;

               2. 如果你确定HashMap的使用的过程中,大小会非常大,那么你应该控制好 加载因子的大小,尽量将它设置得大些。避免Entry[] table过大,而利用率觉很低。

 

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * Rehashes the contents of this map into a new array with a 
  3.  * larger capacity.  This method is called automatically when the 
  4.  * number of keys in this map reaches its threshold. 
  5.  * 
  6.  * If current capacity is MAXIMUM_CAPACITY, this method does not 
  7.  * resize the map, but sets threshold to Integer.MAX_VALUE. 
  8.  * This has the effect of preventing future calls. 
  9.  * 
  10.  * @param newCapacity the new capacity, MUST be a power of two; 
  11.  *        must be greater than current capacity unless current 
  12.  *        capacity is MAXIMUM_CAPACITY (in which case value 
  13.  *        is irrelevant). 
  14.  */  
  15. void resize(int newCapacity) {  
  16.     Entry[] oldTable = table;  
  17.     int oldCapacity = oldTable.length;  
  18.     if (oldCapacity == MAXIMUM_CAPACITY) {  
  19.         threshold = Integer.MAX_VALUE;  
  20.         return;  
  21.     }  
  22.   
  23.     Entry[] newTable = new Entry[newCapacity];  
  24.     transfer(newTable);  
  25.     table = newTable;  
  26.     threshold = (int)(newCapacity * loadFactor);  
  27. }  
  28.   
  29. /** 
  30.  * Transfers all entries from current table to newTable. 
  31.  */  
  32. void transfer(Entry[] newTable) {  
  33.     Entry[] src = table;  
  34.     int newCapacity = newTable.length;  
  35.     for (int j = 0; j < src.length; j++) {  
  36.         Entry<K,V> e = src[j];  
  37.         if (e != null) {  
  38.             src[j] = null;  
  39.             do {  
  40.                 Entry<K,V> next = e.next;  
  41.                 int i = indexFor(e.hash, newCapacity);  
  42.                 e.next = newTable[i];  
  43.                 newTable[i] = e;  
  44.                 e = next;  
  45.             } while (e != null);  
  46.         }  
  47.     }  
  48. }  

 


 

 

为什么JDK建议我们重写Object.equals(Object obj)方法时,需要保证对象可以返回相同的hashcode值?

Java程序员都看过JDK的API文档,该文档关于Object.equals(Object obj)方法,有这样的描述:

   “注意:当此方法被重写时,通常有必要重写hashCode 方法,以维护hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码。

读者虽然知道这个协定,但是不一定真正知道为什么会有这一个要求,现在,就来看看原因吧。

请读者再注意看一下上述的额put()方法实现,当遍历某个桶中的Entry<Key,Value>链表来查找Entry实例的过程中所使用的判断条件:

 

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. for (Entry<K,V> e = table[i]; e != null; e = e.next) {  
  2.             Object k;  
  3.             //5. 查找Entry<Key,Value>链表中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,  
  4.             //已经存在,则将Value值覆盖到对应的Entry<Key,Value>对象节点上  
  5.             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {  
  6.                 V oldValue = e.value;  
  7.                 e.value = value;  
  8.                 e.recordAccess(this);  
  9.                 return oldValue;  
  10.             }  
  11.         }  
对于给定的Key,Value,判断该Key是否与Entry链表中有某一个Entry对象的Key值相等使用的是(k==e.key)==key) || key.equals(k),另外还有一个判断条件:即Key经过hash函数转换后的hash值和当前Entry对象的hash属性值相等(该hash属性值和Entry内的Key经过hash方法转换后的hash值相等)。

 

    上述的情况我们可以总结为;HashMap在确定Key是否在HashMap中存在的要求有两个:

           1. Key值是否相等;

      2. hashcode是否相等;

      所以我们在定义类时,如果重写了equals()方法,但是hashcode却没有保证相等,就会导致当使用该类实例作为Key值放入HashMap中,会出现HashMap“工作异常”的问题,会出现你不希望的情况。下面让我们通过一个例子来看看这个“工作异常”情况:

例子: 定义一个简单Employee类,重写equals方法,而没有重写hashCode()方法。然后使用该类创建两个实例,放置到一个HashMap中:

 

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. package com.louis.hashlearning;  
  2.   
  3. /** 
  4.  * 简单Employee Bean,重写equals方法,未重写hashCode()方法 
  5.  * @author louluan 
  6.  */  
  7. public class Employee {  
  8.       
  9.     private String employeeCode;  
  10.     private String name;  
  11.       
  12.     public Employee(String employeeCode, String name) {  
  13.         this.employeeCode = employeeCode;  
  14.         this.name = name;  
  15.     }  
  16.       
  17.     public String getEmployeeCode() {  
  18.         return employeeCode;  
  19.     }  
  20.     public String getName() {  
  21.         return name;  
  22.     }  
  23.       
  24.     @Override  
  25.     public boolean equals(Object o)  
  26.     {  
  27.         if(o instanceof Employee)  
  28.         {  
  29.             Employee e = (Employee)o;  
  30.             if(this.employeeCode.equals(e.getEmployeeCode()) && name.equals(e.getName()))  
  31.             {  
  32.                 return true;  
  33.             }  
  34.         }  
  35.         return false;  
  36.     }  
  37. }  
[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. package com.louis.hashlearning;  
  2. import java.util.HashMap;  
  3.   
  4. public class Test {  
  5.       
  6.     public static void main(String[] args) {  
  7.         Employee em1= new Employee("123","louis");  
  8.         Employee em2= new Employee("123","louis");  
  9.         boolean equals= em1.equals(em2);  
  10.         System.out.println("em1 equals em2 ? " +equals);  
  11.           
  12.         HashMap map = new HashMap();  
  13.         map.put(em1, "test1");  
  14.         map.put(em2, "test2");  
  15.         System.out.println("map size:"+map.size());  
  16.     }  
  17.   
  18. }  
 输出结果:


 

   结果分析:

        上述的例子中,我们使用了new Employee("123","louis"); 语句创建了两个完全一样的对象em1,em2,对我们来说,它们就是相同的对象,然后,我们将这两个我们认为相等的对象作为Key值放入HashMap中,我们想要的结果是:HashMap中的Entry<Key,Value>键值对数目应该就一个,并且Entry对象的Value值应该是由"test1" 替换成"test2",但是实际的结果是:HashMap的大小为2,即HashMap中有两个Entry<Key,Value>键值对!!!

        原因现在读者清晰了:因为em1和em2对象的hashCode()继承自Object,它们返回两个不同的值,即em1 和em2的hashcode值不相同。

从上面的这个例子可以看出:

         我们重写Object.equals(Object obj)方法时,需要保证对象可以返回相同的hashcode。否则,HashMap工作的时候会有不可控的异常情况出现。

 

            

     2.   get() 方法的实现:

            根据特定的Key值从HashMap中取Value的结果就比较简单了:          

get()方法-根据Key从HashMap中取Value

a.  获取这个Key的hashcode值,根据此hashcode值决定应该从哪一个桶中查找;

b.  遍历所在桶中的Entry<Key,Value>链表,查找其中是否已经有了以Key值为Key存储的Entry<Key,Value>对象,

c1. 若已存在,定位到对应的Entry<Key,Value>,返回value

c2. 若不存在,返回null;

 

具体算法如下:

 

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * Returns the value to which the specified key is mapped, 
  3.  * or {@code null} if this map contains no mapping for the key. 
  4.  *  返回key对应的Value值,如果HashMap中没有,则返回null; 
  5.  *  支持Key为null情况 
  6.  * <p>More formally, if this map contains a mapping from a key 
  7.  * {@code k} to a value {@code v} such that {@code (key==null ? k==null : 
  8.  * key.equals(k))}, then this method returns {@code v}; otherwise 
  9.  * it returns {@code null}.  (There can be at most one such mapping.) 
  10.  * 
  11.  * <p>A return value of {@code null} does not <i>necessarily</i> 
  12.  * indicate that the map contains no mapping for the key; it's also 
  13.  * possible that the map explicitly maps the key to {@code null}. 
  14.  * The {@link #containsKey containsKey} operation may be used to 
  15.  * distinguish these two cases. 
  16.  * 
  17.  * @see #put(Object, Object) 
  18.  */  
  19. public V get(Object key) {  
  20.     if (key == null)  
  21.         return getForNullKey();  
  22.     int hash = hash(key.hashCode());  
  23.     //遍历列表  
  24.     for (Entry<K,V> e = table[indexFor(hash, table.length)];  
  25.          e != null;  
  26.          e = e.next) {  
  27.         Object k;  
  28.         if (e.hash == hash && ((k = e.key) == key || key.equals(k)))  
  29.             return e.value;  
  30.     }  
  31.     return null;  
  32. }  

 

      3.HashMap对Key为null情况的支持

             HashMap允许Key以null的形式存取,Hashmap会将Key为null组成的Entry<null,Value>放置到table[0],即第一个桶中,在put()和get()操作时,会先对Key 为null的值特殊处理:

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * Offloaded version of get() to look up null keys.  Null keys map 
  3.  * to index 0.  This null case is split out into separate methods 
  4.  * for the sake of performance in the two most commonly used 
  5.  * operations (get and put), but incorporated with conditionals in 
  6.  * others. 
  7.  * get 操作 
  8.  */  
  9. private V getForNullKey() {  
  10.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
  11.         if (e.key == null)  
  12.             return e.value;  
  13.     }  
  14.     return null;  
  15. }  

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * Key 为null,则将Entry<null,Value>放置到第一桶table[0]中 
  3.  */  
  4. private V putForNullKey(V value) {  
  5.     for (Entry<K,V> e = table[0]; e != null; e = e.next) {  
  6.         if (e.key == null) {  
  7.             V oldValue = e.value;  
  8.             e.value = value;  
  9.             e.recordAccess(this);  
  10.             return oldValue;  
  11.         }  
  12.     }  
  13.     modCount++;  
  14.     addEntry(0null, value, 0);  
  15.     return null;  
  16. }  

     4. 键值对Entry<Key,Value>的移除----remove(key)方法的实现

 

根据key值移除键值对的操作也比较简单,内部关键的流程分为两个:

1. 根据Key的hashcode 值和Key定位到Entry<key,Value> 对象在HashMap中的位置;

2. 由于Entry<Key,Value>是一个链表元素,之后便是链表删除节点的操作了;

 

[java] view plain copy
 
 print?在CODE上查看代码片派生到我的代码片
  1. /** 
  2.  * Removes the mapping for the specified key from this map if present. 
  3.  * 
  4.  * @param  key key whose mapping is to be removed from the map 
  5.  * @return the previous value associated with <tt>key</tt>, or 
  6.  *         <tt>null</tt> if there was no mapping for <tt>key</tt>. 
  7.  *         (A <tt>null</tt> return can also indicate that the map 
  8.  *         previously associated <tt>null</tt> with <tt>key</tt>.) 
  9.  */  
  10. public V remove(Object key) {  
  11.     Entry<K,V> e = removeEntryForKey(key);  
  12.     return (e == null ? null : e.value);  
  13. }  
  14.   
  15. /** 
  16.  * Removes and returns the entry associated with the specified key 
  17.  * in the HashMap.  Returns null if the HashMap contains no mapping 
  18.  * for this key. 
  19.  */  
  20. final Entry<K,V> removeEntryForKey(Object key) {  
  21.     int hash = (key == null) ? 0 : hash(key.hashCode());  
  22.     int i = indexFor(hash, table.length);  
  23.     Entry<K,V> prev = table[i];  
  24.     Entry<K,V> e = prev;  
  25.   
  26.     while (e != null) {  
  27.         Entry<K,V> next = e.next;  
  28.         Object k;  
  29.         if (e.hash == hash &&  
  30.             ((k = e.key) == key || (key != null && key.equals(k)))) {  
  31.             modCount++;  
  32.             size--;  
  33.             if (prev == e)  
  34.                 table[i] = next;  
  35.             else  
  36.                 prev.next = next;  
  37.             e.recordRemoval(this);  
  38.             return e;  
  39.         }  
  40.         prev = e;  
  41.         e = next;  
  42.     }  
  43.   
  44.     return e;  
  45. }  

 

4. HashMap的特点总结:

        1. HashMap是线程不安全的,如果想使用线程安全的,可以使用Hashtable;它提供的功能和Hashmap基本一致。HashMap实际上是一个Hashtable的轻量级实现;

      2. 允许以Key为null的形式存储<null,Value>键值对;

      3. HashMap的查找效率非常高,因为它使用Hash表对进行查找,可直接定位到Key值所在的桶中;

      4. 使用HashMap时,要注意HashMap容量和加载因子的关系,这将直接影响到HashMap的性能问题。加载因子过小,会提高HashMap的查找效率,但同时也消耗了大量的内存空间,加载因子过大,节省了空间,但是会导致HashMap的查找效率降低。

 

本页内容版权归属为原作者,如有侵犯您的权益,请通知我们删除。

波浪文字 - 2016-09-25 14:09:08

最近写了一段波浪文字代码 /* dkplus专业搜集和编写实用电脑软件教程,搜集各种软件资源和计算机周边(java网络编程,seo网站优化,web开发,lnmp,java网络编程,毕业论文设计),独立制作视频和ppt和音频微信公众号,点击进入 dkplus官方博客http://dkplus.iteye.com 微信搜索dkplus关注公众号可获取海量计算机周边资源。 */ import java.awt.*;import java.applet.*;//Download by http://www.cod
一 自动类型转换 1 自动类型转换图   数范围小的向数范围大的进行自动类型转换,如同把小瓶的水倒入大瓶,不会有任何问题。Java支持自动类型转换。 2 代码示例 public class AutoConversion{public static void main(String[] args){int a = 6;// int可以自动转换为float类型float f = a;// 下面将输出6.0System.out.println(f);// 定义一个byte类型的整数变量byte b = 9;//
深刻理解IdentityHashMap: http://donald-draper.iteye.com/blog/2326264 方法说明: public staticK,V MapK,V unmodifiableMap(Map?extendsK,?extendsVm) 返回指定映射的不可修改视图。此方法允许模块为用户提供对内部映射的“只读”访问。 在返回的映射上执行的查询操作将“读完”指定的映射。试图修改返回的映射 (不管是直接修改还是通过其collection视图进行修改)将导致抛出Unsupporte

storm部署详细步骤 - 2016-09-24 19:09:04

1.修改主机名: vim /etc/sysconfig/network NETWORKING=yes HOSTNAME=MASTER   2.修改IP: vim /etc/sysconfig/network-scripts/ifcfg-eth0 BOOTPROTO="static" HWADDR="00:0C:29:FC:62:B6" IPV6INIT="yes" NM_CONTROLLED="yes" ONBOOT="yes" TYPE="Ethernet" UUID="d0731a46-36df-4a
①前端接收enum时,将它放入一个容器script type="text/javascript"var App = {};App.module = 'merchantManage';App.mydata = {"data":[#{list items:memberStatus, as:'status'}{'title':'${status?.title}','name':'${status}'},#{/list}#{list items:memberOperationTypes, as:'target'}
多线程使用的主要目的在于: 1、吞吐量:你做WEB,容器帮你做了多线程,但是他只能帮你做请求层面的。简单的说,可能就是一个请求一个线程。或多个请求一个线程。如果是单线程,那同时只能处理一个用户的请求。 2、伸缩性:也就是说,你可以通过增加CPU核数来提升性能。如果是单线程,那程序执行到死也就利用了单核,肯定没办法通过增加CPU核数来提升性能。 鉴于你是做WEB的,第1点可能你几乎不涉及。那这里我就讲第二点吧。 --举个简单的例子: 假设有个请求,这个请求服务端的处理需要执行3个很缓慢的IO操作(比如数据库

博客搬家咯 - 2016-09-24 14:09:07

博客搬家了,最新地址: http://blog.uyiplus.com

关于java的10个谎言 - 2016-09-24 14:09:07

关于java的10个谎言 面试中总遇到各种奇葩的问题,小编在兄弟连网站上找到了下面的这些都算是比较高级的问题了,面试中一般也很少问到,因为它们可能会把面试者拒之门外。不过你可以自己找个时间来实践一下。 1. System.exit(0)会跳过finally块的执行 System.setSecurityManager(new SecurityManager() {         @Override         public void checkExit(int status) {            

Java 之浅复制和深复制 - 2016-09-24 14:09:07

1 浅复制和深复制区别 浅复制:浅复制只是复制本对象的原始数据类型,如int、float、String,对于数组和对象引用等是不会复制的。因此浅复制是有风险的。 深复制:不但对原始数据类型进行复制,对于对象中的数组和对象引用也做复制的行为,从而达到对对象的完全复制。 2 代码示例 package com;import java.util.ArrayList;public class Test implements Cloneable {// 私有属性private ArrayListString name
在java编程中,经常需要用到同步,而用得最多的也许是synchronized关键字了,下面看看这个关键字的用法。 因为synchronized关键字涉及到锁的概念,所以先来了解一些相关的锁知识。 java的内置锁:每个java对象都可以用做一个实现同步的锁,这些锁成为内置锁。线程进入同步代码块或方法的时候会自动获得该锁,在退出同步代码块或方法时会释放该锁。获得内置锁的唯一途径就是进入这个锁的保护的同步代码块或方法。 java内置锁是一个互斥锁,这就是意味着最多只有一个线程能够获得该锁,当线程A尝试去获得