开发教程您现在的位置:主页 > 开发教程 >

Java中hashmap的分析

发布日期:2018-01-10 09:31

Java中,哈希表中hashmap集合的实现。西安Java培训整理了非常完整的知识,掌握hashmap集合中源码的分析。
1、HashMap概述
  HashMap根据哈希表的 Map 接口的完成。此完成供给一切可选的映射操作,并答应运用 null 值和 null 键。(除了不同步和答应运用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不确保映射的次序,特别是它不确保该次序恒久不变。
  值得注意的是HashMap不是线程安全的,如果想要线程安全的HashMap,能够经过Collections类的静态办法synchronizedMap取得线程安全的HashMap。
 Map map = Collections.synchronizedMap(new HashMap());
2、HashMap的数据结构
  HashMap的底层首要是根据数组和链表来完成的,它之所以有适当快的查询速度首要是因为它是经过核算散列码来决议存储的方位。HashMap中首要是经过key的hashCode来核算hash值的,只需hashCode相同,核算出来的hash值就一样。如果存储的目标对多了,就有可能不同的目标所算出来的hash值是相同的,这就呈现了所谓的hash抵触。学过数据结构的同学都知道,处理hash抵触的办法有许多,HashMap底层是经过链表来处理hash抵触的。
数组的每个元素都是一个单链表的头节点,链表是用来处理抵触的,如果不同的key映射到了数组的同一方位处,就将其放入单链表中。
我们看看HashMap中Entry类的代码:
    /** Entry是单向链表。    
     * 它是 “HashMap链式存储法”对应的链表。    
     *它完成了Map.Entry 接口,即完成getKey(), getValue(), setValue(V value), equals(Object o), hashCode()这些函数  
    **/  
    static class Entry<K,V> implements Map.Entry<K,V> {    
        final K key;    
        V value;    
        // 指向下一个节点    
        Entry<K,V> next;    
        final int hash;    
   
        // 构造函数。    
        // 输入参数包括"哈希值(h)", "键(k)", "值(v)", "下一节点(n)"    
        Entry(int h, K k, V v, Entry<K,V> n) {    
            value = v;    
            next = n;    
            key = k;    
            hash = h;    
        }    
        public final K getKey() {    
            return key;    
        }    
        public final V getValue() {    
            return value;    
        }    
        public final V setValue(V newValue) {    
            V oldValue = value;    
            value = newValue;    
            return oldValue;    
        }    
        // 判断两个Entry是否相等    
        // 若两个Entry的“key”和“value”都相等,则返回true。    
        // 否则,返回false    
        public final boolean equals(Object o) {    
            if (!(o instanceof Map.Entry))    
                return false;    
            Map.Entry e = (Map.Entry)o;    
            Object k1 = getKey();    
            Object k2 = e.getKey();    
            if (k1 == k2 || (k1 != null && k1.equals(k2))) {    
                Object v1 = getValue();    
                Object v2 = e.getValue();    
                if (v1 == v2 || (v1 != null && v1.equals(v2)))    
                    return true;    
            }    
            return false;    
        }    
        // 实现hashCode()    
        public final int hashCode() {    
            return (key==null   ? 0 : key.hashCode()) ^    
                   (value==null ? 0 : value.hashCode());    
        }    
        public final String toString() {    
            return getKey() + "=" + getValue();    
        }   
        // 当向HashMap中添加元素时,绘调用recordAccess()。    
        // 这里不做任何处理    
        void recordAccess(HashMap<K,V> m) {    
        }      
        // 当从HashMap中删除元素时,绘调用recordRemoval()。    
        // 这里不做任何处理    
        void recordRemoval(HashMap<K,V> m) {    
        }    
    }
HashMap其实就是一个Entry数组,Entry对象中包含了键和值,其中next也是一个Entry对象,它就是用来处理hash冲突的,形成一个链表。
3、HashMap源码分析
(1)、要害特点
先看看HashMap类中的一些要害特点:
transient Entry[] table;//存储元素的实体数组
transient int size;//寄存元素的个数
int threshold; //临界值   当实际巨细超越临界值时,会进行扩容threshold = 加载因子*容量
final float loadFactor; //加载因子
transient int modCount;//被修正的次数
其间loadFactor加载因子是表示Hsah表中元素的填满的程度.
若:加载因子越大,填满的元素越多,优点是,空间利用率高了,但:抵触的时机加大了.链表长度会越来越长,查找功率下降。
反之,加载因子越小,填满的元素越少,优点是:抵触的时机减小了,但:空间糟蹋多了.表中的数据将过于稀疏(许多空间还没用,就开始扩容了)
抵触的时机越大,则查找的本钱越高.
因而,必须在 "抵触的时机"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"对立的平衡与折衷.
  如果机器内存满足,并且想要提高查询速度的话能够将加载因子设置小一点;相反如果机器内存严重,并且对查询速度没有什么要求的话能够将加载因子设置大一点。不过一般我们都不用去设置它,让它取默认值0.75就好了。
(2)、结构办法
下面看看HashMap的几个构造方法:
public HashMap(int initialCapacity, float loadFactor) {
//确保数字合法
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;   //初始容量
while (capacity < initialCapacity)   //确保容量为2的n次幂,使capacity为大于initialCapacity的最小的2的n次幂
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
我们能够看到在结构HashMap的时分如果我们指定了加载因子和初始容量的话就调用第一个结构办法,不然的话就是用默许的。默许初始容量为16,默许加载因子为0.75。我们能够看到上面代码中13-15行,这段代码的作用是保证容量为2的n次幂,使capacity为大于initialCapacity的最小的2的n次幂,至于为什么要把容量设置为2的n次幂,我们等下再看。
要点剖析下HashMap顶用的最多的两个办法put和get
     (3)、存储数据
  下面看看HashMap存储数据的进程是怎样的,首要看看HashMap的put办法:
public V put(K key, V value) {
     // 若“key为null”,则将该键值对添加到table[0]中。
         if (key == null)
            return putForNullKey(value);
     // 若“key不为null”,则计算该key的哈希值,然后将其添加到该哈希值对应的链表中。
         int hash = hash(key.hashCode());
     //搜索指定hash值在对应table中的索引
         int i = indexFor(hash, table.length);
     // 循环遍历Entry数组,若“该key”对应的键值对已经存在,则用新的value取代旧的value。然后退出!
         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))) { //如果key相同则覆盖并返回旧值
                  V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
              }
         }
     //修改次数+1
         modCount++;
     //将key-value添加到table[i]处
     addEntry(hash, key, value, i);
     return null;
}
上面程序顶用到了一个重要的内部接口:Map.Entry,每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出:当体系决议存储 HashMap 中的 key-value 对时,完全没有考虑 Entry 中的 value,仅仅只是根据 key 来计算并决议每个 Entry 的存储方位。这也说明了前面的结论:我们完全可以把 Map 调集中的 value 当成 key 的附属,当体系决议了 key 的存储方位之后,value 随之保存在那里即可。
我们慢慢的来剖析这个函数,第2和3行的效果就是处理key值为null的状况,我们看看
putForNullKey(value)方法:
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {   //如果有key为null的对象存在,则覆盖掉
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0); //如果键为null的话,则hash值为0
return null;
}
注意:如果key为null的话,hash值为0,对象存储在数组中索引为0的位置。即table[0]
我们再回去看看put方法中第4行,它是通过key的hashCode值计算hash码,下面是计算hash码的函数:
//计算hash值的方法 通过键的hashCode来计算
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);
}
得到hash码之后就会通过hash码去核算出应该存储在数组中的索引,核算索引的函数如下:
static int indexFor(int h, int length) { //依据hash值和数组长度算出索引值
return h & (length-1);  //这儿不能随意算取,用hash&(length-1)是有原因的,这样可以保证算出来的索引是在数组巨细范围内,不会超出
}
这个我们要要点说下,我们一般对哈希表的散列很自然地会想到用hash值对length取模(即除法散列法),Hashtable中也是这样完结的,这种方法基本能保证元素在哈希表中散列的比较均匀,但取模会用到除法运算,功率很低,HashMap中则通过h&(length-1)的方法来替代取模,相同完结了均匀的散列,但功率要高许多,这也是HashMap对Hashtable的一个改进。
    接下来,我们分析下为什么哈希表的容量必定要是2的整数次幂。首要,length为2的整数次幂的话,h&(length-1)就相当于对length取模,这样便保证了散列的均匀,同时也提升了功率;其次,length为2的整数次幂的话,为偶数,这样length-1为奇数,奇数的终究一位是1,这样便保证了h&(length-1)的终究一位可能为0,也可能为1(这取决于h的值),即与后的效果可能为偶数,也可能为奇数,这样便可以保证散列的均匀性,而如果length为奇数的话,很明显length-1为偶数,它的终究一位是0,这样h&(length-1)的终究一位肯定为0,即只能为偶数,这样任何hash值都只会被散列到数组的偶数下标方位上,这便浪费了近一半的空间,因此,length取2的整数次幂,是为了使不同hash值发作碰撞的概率较小,这样就能使元素在哈希表中均匀地散列。
  这看上去很简单,其实比较有玄机的,我们举个例子来说明:
  假设数组长度分别为15和16,优化后的hash码分别为8和9,那么&运算后的效果如下: 
       h & (table.length-1)                     hash                             table.length-1
       8 & (15-1):                                 0100                   &              1110                   =                0100
       9 & (15-1):                                 0101                   &              1110                   =                0100
       -----------------------------------------------------------------------------------------------------------------------
       8 & (16-1):                                 0100                   &              1111                   =                0100
       9 & (16-1):                                 0101                   &              1111                   =                0101

从上面的例子中能够看出:当它们和15-1(1110)“与”的时分,产生了相同的成果,也就是说它们会定位到数组中的同一个方位上去,这就产生了磕碰,8和9会被放到数组中的同一个方位上构成链表,那么查询的时分就需要遍历这个链 表,得到8或许9,这样就降低了查询的功率。一起,我们也能够发现,当数组长度为15的时分,hash值会与15-1(1110)进行“与”,那么 最终一位永久是0,而0001,0011,0101,1001,1011,0111,1101这几个方位永久都不能寄存元素了,空间浪费相当大,更糟的是这种状况中,数组能够使用的方位比数组长度小了许多,这意味着进一步增加了磕碰的几率,减慢了查询的功率!而当数组长度为16时,即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1,这使得在低位上&时,得到的和原hash的低位相同,加之hash(int h)办法对key的hashCode的进一步优化,参加了高位计算,就使得只要相同的hash值的两个值才会被放到数组中的同一个方位上构成链表。
   所以说,当数组长度为2的n次幂的时分,不同的key算得得index相同的几率较小,那么数据在数组上散布就比较均匀,也就是说磕碰的几率小,相对的,查询的时分就不必遍历某个方位上的链表,这样查询功率也就较高了。
       根据上面 put 办法的源代码能够看出,当程序试图将一个key-value对放入HashMap中时,程序首要根据该 key 的 hashCode() 回来值决议该 Entry 的存储方位:如果两个 Entry 的 key 的 hashCode() 回来值相同,那它们的存储方位相同。如果这两个 Entry 的 key 经过 equals 比较回来 true,新增加 Entry 的 value 将掩盖调集华夏有 Entry 的 value,但key不会掩盖。如果这两个 Entry 的 key 经过 equals 比较回来 false,新增加的 Entry 将与调集华夏有 Entry 构成 Entry 链,而且新增加的 Entry 位于 Entry 链的头部——详细阐明继续看 addEntry() 办法的阐明。
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<k,v> e = table[bucketIndex]; //如果要参加的方位有值,将该方位原先的值设置为新entry的next,也就是新entry链表的下一个节点
table[bucketIndex] = new Entry<>(hash, key, value, e);
if (size++ >= threshold) //如果大于临界值就扩容
resize(2 * table.length); //以2的倍数扩容
}
参数bucketIndex就是indexFor函数计算出来的索引值,第2行代码是获得数组中索引为bucketIndex的Entry目标,第3行就是用hash、key、value构建一个新的Entry目标放到索引为bucketIndex的方位,而且将该方位原先的目标设置为新目标的next构成链表。
第4行和第5行就是判别put后size是否达到了临界值threshold,如果达到了临界值就要进行扩容,HashMap扩容是扩为本来的两倍。
(4)、调整巨细
resize()办法如下:
 从头调整HashMap的巨细,newCapacity是调整后的单

void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);//用来将原先table的元素全部移到newTable里面
table = newTable;  //再将newTable赋值给table
threshold = (int)(newCapacity * loadFactor);//重新计算临界值
}
新建了一个HashMap的底层数组,上面代码中第10行为调用transfer办法,将HashMap的全部元素添加到新的HashMap中,并从头核算元素在新的数组中的索引方位
当HashMap中的元素越来越多的时分,hash冲突的几率也就越来越高,由于数组的长度是固定的。所以为了进步查询的功率,就要对HashMap的数组进行扩容,数组扩容这个操作也会呈现在ArrayList中,这是一个常用的操作,而在HashMap数组扩容之后,最耗费功能的点就呈现了:原数组中的数据有必要从头核算其在新数组中的方位,并放进去,这就是resize。
   那么HashMap什么时分进行扩容呢?当HashMap中的元素个数超越数组巨细*loadFactor时,就会进行数组扩容,loadFactor的默许值为0.75,这是一个折中的取值。也就是说,默许情况下,数组巨细为16,那么当HashMap中元素个数超越16*0.75=12的时分,就把数组的巨细扩展为 2*16=32,即扩大一倍,然后从头核算每个元素在数组中的方位,扩容是需求进行数组仿制的,仿制数组是十分耗费功能的操作,所以如果我们现已预知HashMap中元素的个数,那么预设元素的个数能够有用的进步HashMap的功能。
 (5)、数据读取
public V get(Object key) {   
if (key == null)   
return getForNullKey();   
int hash = hash(key.hashCode());   
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.equals(k)))   
return e.value;   
 }   
 return null;   
}  
有了上面存储时的hash算法作为基础,了解起来这段代码就很简单了。从上面的源代码中能够看出:从HashMap中get元素时,首要核算key的hashCode,找到数组中对应方位的某一元素,然后通过key的equals方法在对应方位的链表中找到需求的元素。
(6)、HashMap的性能参数:
   HashMap 包括如下几个结构器:
   HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
   HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。
   HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
   HashMap的基础结构器HashMap(int initialCapacity, float loadFactor)带有两个参数,它们是初始容量initialCapacity和加载因子loadFactor。
   initialCapacity:HashMap的最大容量,即为底层数组的长度。
   loadFactor:负载因子loadFactor界说为:散列表的实践元素数目(n)/ 散列表的容量(m)。
   负载因子衡量的是一个散列表的空间的运用程度,负载因子越大标明散列表的装填程度越高,反之愈小。关于运用链表法的散列表来说,查找一个元素的均匀时间是O(1+a),因此如果负载因子越大,对空间的运用更充分,可是结果是查找功率的下降;如果负载因子太小,那么散列表的数据将过于稀疏,对空间形成严峻浪费。
   HashMap的完成中,通过threshold字段来判别HashMap的最大容量:
threshold = (int)(capacity * loadFactor);  
   结合负载因子的界说公式可知,threshold就是在此loadFactor和capacity对应下容许的最大元素数目,超越这个数目就从头resize,以下降实践的负载因子。默许的的负载因子0.75是对空间和时间功率的一个平衡挑选。当容量超出此最大容量时, resize后的HashMap容量是容量的两倍。