深入浅出--HashMap

zqhxuyuan 贡献于2013-04-11

作者 Administrator  创建于2008-09-11 17:20:00   修改者雨林木风  修改于2012-06-08 07:39:00字数20359

文档摘要:HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键. 此类不保证映射的顺序,特别是它不保证该顺序恒久不变.
关键词:

Hash:散列/哈希 把任意长度的输入,通过散列算法,变换成固定长度的输出,该输出就是散列值(hashcode). 这种转换是一种压缩映射,散列值的空间通常远小于输入的空间, 不同的输入可能会散列成相同的输出,而不可能从散列值来唯一的确定输入值. 简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数. HashMap是基于哈希表的Map接口的非同步实现.此实现提供所有可选的映射操作,并允许使用null值和null键. 此类不保证映射的顺序,特别是它不保证该顺序恒久不变. HashMap的数据结构: JAVA中最基本的结构:数组+模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的. Hashmap实际上是一个数组和链表的结合体(链表散列),下图横排表示数组,纵排表示数组元素(实际上是一个链表). 1.通过hashcode找到数组中的某一个元素 2.通过key的equals方法在链表中找到key对应的value 初始化数组 HashMap底层就是一个数组结构,数组中的每一项又是一个链表存储[key-value键值对的Entry的数组]. 当新建一个hashmap的时候,就会初始化一个数组. public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR); table = new Entry[DEFAULT_INITIAL_CAPACITY]; //初始化数组 init(); } /** * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table; static class Entry implements Map.Entry { final K key; V value; Entry next; final int hash; } 上面的Entry就是数组中的元素[table这个数组存储的并非是单纯的键值对,实际存储的是链表], 它持有一个指向下一个元素的引用[每一个Entry的next将指向该链表的下一个元素],这就构成了链表. HashMap主要是用数组来存储数据的,它会对key进行哈希运算,哈希运算会有重复的哈希值,对于哈希值的冲突,HashMap采用链表来解决的.next就是为了哈希冲突而存在的.比如通过哈希运算,一个新元素应该在数组的第10个位置,但是第10个位置已经有Entry,那么好吧,将新加的元素也放到第10个位置,将第10个位置的原有Entry赋值给当前新加的 Entry的next属性. 数组存储的是链表,链表是为了解决哈希冲突的. entry实际上是在实现单向链表结构,每一个entry内部有一个next指向他的后面,所以hashmap的内部数组每个格子存放的是实际上是一个链表的火车头,在最开始的时候table[index]位置上肯定是null,这个就是火车尾了。 所以get的时候查找操作是以null为循环终点判断依据的。在插入的时候把新加的元素替代原来的成为链表火车头,把之前元素的放在新加的火车头后面,这么做是因为不同的key是有可能算出相同的hash值的,这种情况的时候,他们都会存放在数组的同一个index位置上,相同的hash不同的key的值彼此用链表连接起来. 几个关键的属性 /** * The default initial capacity - MUST be a power of two. 默认容量 */ static final int DEFAULT_INITIAL_CAPACITY = 16; /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. 最大容量 */ static final int MAXIMUM_CAPACITY = 1 << 30; /**默认加载因子,加载因子是一个比例,当HashMap的数据大小>=容量*加载因子时,HashMap会将容量扩容 * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /**存储数据的数组 * The table, resized as necessary. Length MUST Always be a power of two. */ transient Entry[] table; /** * The number of key-value mappings contained in this map. */ transient int size; /**当实际数据大小超过threshold时,HashMap会将容量扩容,threshold=容量*加载因子 * The next size value at which to resize (capacity * load factor). * @serial */ int threshold; /**加载因子 * The load factor for the hash table. */ final float loadFactor; /** * The number of times this HashMap has been structurally modified * Structural modifications are those that change the number of mappings in * the HashMap or otherwise modify its internal structure (e.g., * rehash). This field is used to make iterators on Collection-views of * the HashMap fail-fast. (See ConcurrentModificationException). */ transient volatile int modCount; /** * Constructs an empty HashMap with the specified initial * capacity and load factor. *以指定初始化容量、负载因子创建 HashMap * @param initialCapacity the initial capacity * @param loadFactor the load factor * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ 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)) // 负载因子必须大于 0 的数值 throw new IllegalArgumentException(“Illegal load factor: “ + loadFactor); // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) // 计算出大于 initialCapacity 的最小的 2 的 n 次方值 capacity <<= 1; //不管你希望的初始长度是多少,系统都是对1做移位运算,最后的结果只能是2的次方 this.loadFactor = loadFactor; threshold = (int)(capacity * loadFactor); //计算实际容量:设置容量极限等于容量 * 负载因子 table = new Entry[capacity]; // 初始化table数组 init();//留给子类实现的一些操作,默认空 } 当创建一个 HashMap 时,系统会自动创建一个 table 数组来保存 HashMap 中的 Entry table 其实就是一个普通数组,每个数组都有一个固定的长度,这个数组的长度就是 HashMap 的容量 capacity才是初始容量,而不是initialCapacity. 找出大于 initialCapacity 的、最小的 2 的 n 次方值,并将其作为 HashMap 的实际容量(由 capacity 变量保存). 例如给定 initialCapacity 为 9: 执行new HashMap(9,0.75)那么该 HashMap 的实际容量/初始容量就是16,而不是9. HashMap(int initialCapacity, float loadFactor) int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; capacity从1开始和传入的initialCapacity比较,小于的话则每次*2(<<= 1). 1*2=2<9; 2*2=4<9; 4*2=8<9; 8*2=16 capacity=16>9. 停止while 对于 HashMap 及其子类而言,它们采用 Hash 算法来决定集合中元素的存储位置.当系统开始初始化 HashMap 时,系统会创建一个长度为 capacity 的 Entry 数组,这个数组里可以存储元素的位置被称为“桶(bucket)”,每个 bucket 都有其指定索引,系统可以根据索引快速访问该 bucket 里存储的元素. 无论何时,HashMap 的每个“桶”只存储一个元素(也就是一个 Entry),由于 Entry 对象可以包含一个引用变量(就是 Entry 构造器的的最后一个参数)用于指向下一个 Entry,因此可能出现的情况是:HashMap 的 bucket 中只有一个 Entry,但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链 Hash算法和索引位置 /** * Initialization hook for subclasses. This method is called * in all constructors and pseudo-constructors (clone, readObject) * after HashMap has been initialized but before any entries have * been inserted. (In the absence of this method, readObject would * require explicit knowledge of subclasses.) */ void init() { } /** * Applies a supplemental hash function to a given hashCode, which * defends against poor quality hash functions. This is critical * because HashMap uses power-of-two length hash tables, that * otherwise encounter collisions for hashCodes that do not differ * in lower bits. Note: Null keys always map to hash 0, thus index 0. */ 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(int h)方法根据key的hashCode重新计算一次散列. 防止key本身的hashcode实现很差. 此算法加入了高位计算,防止低位不变,高位变化时,造成的hash冲突 // Returns index for hash code h. static int indexFor(int h, int length) { return h & (length-1); } 我们可以看到在HashMap中要找到某个元素,需要根据key的hash值来求得对应数组中的位置.如何计算这个位置就是hash算法. HashMap的数据结构是数组和链表的结合,所以我们希望HashMap里面的元素位置尽量的分布均匀些,尽量使得每个位置上的元素数量只有一个,那么当我们用hash算法求得这个位置的时候,马上就可以知道对应位置的元素就是我们要的,而不用再去遍历链表,这样就大大优化了查询的效率. 对于任意给定的对象,只要它的hashCode()返回值相同,那么程序调用hash(int h)方法所计算得到的hash码值总是相同的. 首先想到把hash值对数组长度取模运算(hash%length),这样一来元素的分布相对来说是比较均匀.但是”模”运算的消耗比较大. 能不能找一种更快速,消耗更小的方式?在HashMap中是这样做的:调用indexFor(int h, int length)方法来计算该对象应该保存在table数组的哪个索引处.这个方法通过h&(table.length-1)来得到该对象的保存位,而HashMap底层数组的长度总是2的n次方,这是HashMap在速度上的优化. 首先算得key的hashcode值,然后跟数组的长度-1做一次”与”运算(&). 比如数组的长度是2的4次方,那么hashcode就会和2的4次方-1做”与”运算. 很多人都有这个疑问,为什么hashmap的数组初始化大小都是2的次方大小时,hashmap的效率最高, 我以2的4次方举例,来解释一下为什么数组大小为2的幂时hashmap访问的性能最高.  左边两组是数组长度为16(2的4次方),右边两组是数组长度为15.两组的优化后的hash码均为8和9.   h & (table.length-1)      hash      table.length-1 index        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)”与”的时候,产生了相同的结果,也就是说它们会定位到数组中的同一个位置上去,这就产生了碰撞(hash冲突),8和9会被放到数组中的同一个位置上形成链表,那么查询的时候就需要遍历这个链表,得到8或者9,这样就降低了查询的效率.同时我们也可以发现,当数组长度为15的时候,hash值会与15-1(1110)进行”与”,那么最后一位永远是0,而0001,0011,0101,0111,1001,1011,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率! 当数组长度为16时,即为2的n次方时,2n-1得到的二进制数的每个位上的值都为1,这使得在低位上&时,得到的和原hash的低位相同. 加之hash(int h)方法对key的hashCode的进一步优化,加入了高位计算,就使得只有相同的hash值的两个值才会被放到数组中的同一个位置上形成链表. 所以说,当数组长度为2的n次幂的时候,不同的key算得得index相同的几率较小,那么数据在数组上分布就比较均匀,也就是说碰撞的几率小,相对的,查询的时候就不用遍历某个位置上的链表,这样查询效率也就较高了.  回头看一下hashmap中默认的数组大小是多少,查看源代码可以得知是16,为什么是16,而不是15,也不是20呢,显然是因为16是2的整数次幂的原因,在小数据量的情况下16比15和20更能减少key之间的碰撞,而加快查询的效率.  所以,在存储大容量数据的时候,最好预先指定hashmap的size为2的整数次幂次方.就算不指定的话,也会以大于且最接近指定值大小的2次幂来初始化的.在HashMap构造器中有如下代码: // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1;  这段代码保证初始化时HashMap的容量总是2的n次方,即底层数组的长度总是为2的n次方. 当length总是 2 的n次方时,h&(length-1)运算等价于对length取模,也就是h%length,但是&比%具有更高的效率. 当 length 总是 2 的倍数时,h & (length-1) 将是一个非常巧妙的设计:假设 h=5,length=16, 那么 h & length - 1 将得到 5;如果 h=6,length=16, 那么 h & length - 1 将得到 6 ……如果 h=15,length=16, 那么 h & length - 1 将得到 15;但是当 h=16 时 , length=16 时,那么 h & length - 1 将得到 0 了;当 h=17 时 , length=16 时,那么 h & length - 1 将得到 1 了……这样保证计算得到的索引值总是位于 table 数组的索引之内. HashMap的存(put)实现 /** * Associates the specified value with the specified key in this map. * If the map previously contained a mapping for the key, the old * value is replaced.关联Map的key和value.如果key已经存在,旧的value会被覆盖 * 返回null或者被覆盖前的value * @param key key with which the specified value is to be associated * @param value value to be associated with the specified key * @return the previous value associated with key, or * null if there was no mapping for key. * (A null return can also indicate that the map * previously associated null with key.) */ public V put(K key, V value) { //HashMap允许存放null键和null值. //当key为null时,调用putForNullKey方法,将value放置在数组第一个位置 if (key == null) return putForNullKey(value); //获取key的hash值, 根据key的keyCode重新计算hash值 int hash = hash(key.hashCode()); //新元素插入HashMap的位置由其hash值决定.搜索指定hash值在对应table中的索引. //通过hash值和table长度算出该key的hash值所对应的table数组索引index:i int i = indexFor(hash, table.length); //遍历table[i]这个位置的链表. 如果i索引处的Entry不为null,通过循环不断遍历e元素的下一个元素 for (Entry e = table[i]; e != null; e = e.next) { Object k; //如果hash值与key都相同,表明该链表中已存在该key的entry,则更新该entry的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; //临时变量:oldValue.最后返回oldValue e.value = value; //新put进来的value作为entry最新的value e.recordAccess(this); return oldValue; } } //若程序走到这里,table[i]处尚没有该key对应的entry: //i索引处的Entry为null,表明此处还没有Entry,插入entry modCount++; //将key、value添加到i索引处 addEntry(hash, key, value, i); return null; } 往HashMap中put元素时,先根据key的hashCode重新计算hash值,根据hash值得到这个元素在数组中的位置(下标), 如果数组该位置上已经存放有其他元素了,那么在这个位置上的元素将以链表的形式存放,新加入的放在链头,最先加入的放在链尾.如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上. for循环里只是处理有相同key的情况,为的是保持数组里的元素的value值是最新放进来的value. 对于相同的key,显然得到的hash也是一样的.这样key和hash都相同: int hash = hash(key.hashCode()); 才会做替换旧的value为新的value这一步操作: V oldValue = e.value; e.value = value; 结论:往Map中存放元素时,如果key相同,则会发生覆盖. /** * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if appropriate. * 根据计算出的hash值,将key-value对放在数组table的i索引处 * Subclass overrides this to alter the behavior of put method. */ void addEntry(int hash, K key, V value, int bucketIndex) { //获取指定bucketIndex索引处的Entry Entry e = table[bucketIndex]; //将新创建的new Entry()放入bucketIndex索引处,并让新的Entry指向原来的Entry //如果数组该位置上没有元素,就直接将该元素放到此数组中的该位置上,否则以链表形式存放 //新建一个Entry对象,并放在当前位置的Entry链表的头部 table[bucketIndex] = new Entry(hash, key, value, e); //如果Map中的key-value对的数量超过了极限, 把table对象的长度扩充到原来的2倍 if (size++ >= threshold) resize(2 * table.length); } 根据上面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链的头部. 当系统决定存储HashMap中的key-value对时,完全没有考虑Entry中的value,仅仅只是根据key来计算并决定每个Entry的存储位置.我们完全可以把Map集合中的value当成key的附属,当系统决定了key的存储位置之后,value随之保存在那里即可 系统总是将新添加的 Entry 对象放入 table 数组的 bucketIndex 索引处——如果 bucketIndex 索引处已经有了一个 Entry 对象,那新添加的 Entry 对象指向原有的 Entry 对象(产生一个 Entry 链),如果 bucketIndex 索引处没有 Entry 对象,也就是e 变量是 null,也就是新放入的 Entry 对象指向 null,也就是没有产生 Entry 链 当向 HashMap 中添加 key-value 对,由其 key 的 hashCode() 返回值决定该 key-value 对(就是 Entry 对象)的存储位置.当两个 Entry 对象的 key 的 hashCode() 返回值相同时,将由 key 通过 eqauls() 比较值决定是采用覆盖行为(返回 true),还是产生 Entry 链(返回 false) 在同一个 bucket 存储 Entry 链的情况下,新放入的 Entry 总是位于 bucket 中,而最早放入该 bucket 中的 Entry 则位于这个 Entry 链的最末端.上面程序中还有这样两个变量: size:保存了该 HashMap 中所包含的 key-value 对的数量. threshold:包含了HashMap能容纳的 key-value 对的极限,它的值等于 HashMap 的容量乘以负载因子(load factor). 当 size++ >= threshold 时,HashMap 会自动调用 resize 方法扩充 HashMap 的容量.每扩充一次,HashMap 的容量就增大一倍 put方法测试 Map map = new HashMap(); //int oldValue = map.put(“hello”,1); 会报错:java.lang.NullPointerException.因为返回null map.put(“hello”, 1); //key:hello不存在,添加进数组 int oldValue = map.put(“hello”, 2); //key:hello已经存在,最终map为:table[0]==>hello=2 System.out.println(oldValue); //return oldValue:1. map.put(“helloworld”, 3); //key不存在,添加进数组中,由于index=0, //数组该位置已经存在其他元素(hello=2),所以将以链表的形式.新元素在链表的头部,原先的在链尾 map.put(“helloagain”, 4); //index=6,数组该位置上没有元素,就直接将该元素放到此数组中的该位置上 //hashcode hash index index(“helloworld”);//-1524582912 -1372449440 0 index(“helloagain”);//-1545155122 -1466568714 6 当new HashMap时分配给table的数组长度为默认的16,每个元素都是null. map.put(“hello”, 1);时执行addEntry,将key=hello,value=1插入索引0处.数组中只有一个元素.返回null. map.put(“hello”, 2);执行for循环.如果key相同,则新put进来的元素会作为数组最新的值.但返回的是被覆盖前的值. 如果key不相同,则添加进数组中. 执行完后map中只有一个元素table[0]: hello=2 map.put(“helloworld”, 3);调用addEntry(-1372449440,”helloworld”,”3”,0) Entry e = table[bucketIndex]; table[bucketIndex] = new Entry(hash, key, value, e); table[0]这个位置中已经存有table[0]: hello=2元素了,所以将以链表的形式存放: Entry e = table[0] ==> hello=2 table[0] = new Entry(-1372449440,”helloworld”,”3”,e) 新建的Entry对象放在链表的头部,即现在table[0] ==> helloworld=3. -->new Entry的前三个参数 而原先存在的元素放在链表的尾部,即Entry e:hello=2作为helloworld=3的next元素存在. -->最后一个参数 执行后Map中的结果(entrySet)是: [helloworld=3, hello=2]. 同理,当执行map.put(“helloagain”, 4);由于index=6, 数组该位置上没有元素,就直接将该元素放到此数组中的该位置上 执行后Map中的结果(entrySet)是: [helloworld=3, hello=2, helloagain=4].即最终的链表散列如下: helloworld=3 .. helloagain=4 ↓ hello=2 以此类推.当往Map中不断put元素时,如果数组index位置已经存在元素,将以链表的形式存放.否则直接放到数组上. HashMap的取(get)实现 /** * Returns the value to which the specified key is mapped, * or {@code null} if this map contains no mapping for the key. * *

More formally, if this map contains a mapping from a key * {@code k} to a value {@code v} such that {@code (key==null ? k==null : * key.equals(k))}, then this method returns {@code v}; otherwise * it returns {@code null}. (There can be at most one such mapping.) * *

A return value of {@code null} does not necessarily * indicate that the map contains no mapping for the key; it's also * possible that the map explicitly maps the key to {@code null}. * The {@link #containsKey containsKey} operation may be used to * distinguish these two cases. * * @see #put(Object, Object) */ public V get(Object key) { if (key == null) return getForNullKey(); //计算key的hashcode int hash = hash(key.hashCode()); //找到数组中对应位置的某一元素 for (Entry e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //通过key的equals方法在对应位置的链表中找到需要的元素 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } return null; } Map放进去的元素的key在put操作时和get操作时hash(key.hashCode())的返回值hash是不会变的.因此indexFor(hash,table.length)获取数组的索引位置的值也是不会变的.找到索引后,通过数组table[index]定位到元素. 如果是链表结构,则判断key和hash如果相同则说明找到该元素. 从hashmap中get元素时,首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素.从这里我们可以想象得到,如果每个位置上的链表只有一个元素,那么hashmap的get效率将是最高的. get的时候就是算出key的hash值,算出数组的index位置,然后到数组的index位置上去遍历链表找到相应的key, 如果hash重复的少的话,链表的长度就会很短,hashmap查找的速度就很快了, 即使有重复,接下来就是遍历链表,所以要依靠好的算法保证hash重复的概率小,缩短链表的长度. HashMap的元素查找大致分为三步: 1).根据key的hashcode()得到哈希值 2).根据哈希值确定元素在数组中的位置 3).找到指定位置的链表,循环比较,先"=="比较,如果不等,再"equals"比较,如果有一个比较相等,就说明找到元素了. 所以要把一个对象放进HashMap的时候,最好是重写hashcode()方法和equals()方法: 根据前面的分析,hashcode()可以确定元素在数组中的位置,而equals方法在链表的比较时要用到. 当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时,此时的 HashMap 具有最好的性能:当程序通过 key 取出对应 value 时,系统只要先计算出该 key 的 hashCode() 返回值,在根据该 hashCode 返回值找出该 key 在 table 数组中的索引,然后取出该索引处的 Entry,最后返回该 key 对应的 value 即可. 如果 HashMap 的每个 bucket 里只有一个 Entry 时,HashMap 可以根据索引、快速地取出该 bucket 里的 Entry;在发生“Hash 冲突”的情况下,单个 bucket 里存储的不是一个 Entry,而是一个 Entry 链,系统只能必须按顺序遍历每个 Entry,直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端(该 Entry 是最早放入该 bucket 中),那系统必须循环到最后才能找到该元素. HashMap的存取总结 HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry 对象.HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对,当需要存储一个 Entry 对象时,会根据hash算法来决定其在数组中的存储位置,再根据equals方法决定其在该数组位置上的链表中的存储位置; 当需要取出一个 Entry 时,也会根据 Hash 算法找到其在数组中的存储位置,(再根据equals方法从该位置上的链表中)直接取出该 Entry.由此可见:HashMap 之所以能快速存、取它所包含的 Entry,完全类似于现实生活中母亲从小教我们的:不同的东西要放在不同的位置,需要时才能快速找到它. Hashmap扩容/性能参数 HashMap 包含如下几个构造器: HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap. HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap. HashMap(int initialCapacity,float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap[基础构造器]. initialCapacity:HashMap的最大容量,即为底层数组的长度. loadFactor:负载因子loadFactor定义为:散列表的实际元素数目(n)/散列表的容量(m). 负载因子衡量的是一个散列表的空间的使用程度,负载因子越大表示散列表的装填程度越高,反之愈小. 对于使用链表法的散列表来说,查找一个元素的平均时间是O(1+a), 因此如果负载因子越大,对空间的利用更充分,然而后果是查找效率的降低; 如果负载因子太小,那么散列表的数据将过于稀疏,对空间造成严重浪费. HashMap的实现中,通过threshold字段来判断HashMap的最大容量: threshold = (int)(capacity * loadFactor);   结合负载因子的定义公式可知,threshold就是在此loadFactor和capacity对应下允许的最大元素数目, 超过这个数目就重新resize,以降低实际的负载因子.默认的的负载因子0.75是对空间和时间效率的一个平衡选择. 当容量超出此最大容量时, resize后的HashMap容量是容量的两倍: if (size++ >= threshold)      resize(2 * table.length); 当put一个元素时,如果达到了容量限制,HashMap就会扩容,新的容量永远是原来的2倍.当hashmap中的元素越来越多的时候,碰撞的几率也就越来越高(因为数组的长度是固定的),所以为了提高查询的效率,就要对hashmap的数组进行扩容,数组扩容这个操作也会出现在ArrayList中,所以这是一个通用的操作,很多人对它的性能表示过怀疑,不过想想我们的”均摊”原理,就释然了,而在hashmap数组扩容之后,最消耗性能的点就出现了:原数组中的数据必须重新计算其在新数组中的位置,并放进去,这就是resize.  那么hashmap什么时候进行扩容呢?当hashmap中的元素个数超过数组大小*loadFactor时,就会进行数组扩容,loadFactor的默认值为0.75,也就是说,默认情况下,数组大小为16,那么当hashmap中元素个数超过16*0.75=12的时候,就把数组的大小扩展为2*16=32,即扩大一倍,然后重新计算每个元素在数组中的位置,而这是一个非常消耗性能的操作,所以如果我们已经预知hashmap中元素的个数,那么预设元素的个数能够有效的提高hashmap的性能.比如说,我们有1000个元素new HashMap(1000), 但是理论上来讲new HashMap(1024)更合适,不过上面annegu已经说过,即使是1000,hashmap也自动会将其设置为1024. 但是new HashMap(1024)还不是更合适的,因为0.75*1000 < 1000, 也就是说为了让0.75 * size > 1000, 我们必须这样new HashMap(2048)才最合适,既考虑了&的问题,也避免了resize的问题.  /** * Rehashes the contents of this map into a new array with a * larger capacity. This method is called automatically when the * number of keys in this map reaches its threshold. * * If current capacity is MAXIMUM_CAPACITY, this method does not * resize the map, but sets threshold to Integer.MAX_VALUE. * This has the effect of preventing future calls. * * @param newCapacity the new capacity, MUST be a power of two; * must be greater than current capacity unless current * capacity is MAXIMUM_CAPACITY (in which case value * is irrelevant). */ 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; threshold = (int)(newCapacity * loadFactor); } /**tranfer方法将所有的元素重新哈希,因为新的容量变大,所以每个元素的哈希值和位置都是不一样的 * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable) { Entry[] src = table; int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { Entry e = src[j]; if (e != null) { src[j] = null; do { Entry next = e.next; int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } while (e != null); } } } key的hashcode和equals方法重写 get方法的过程:首先计算key的hashcode,找到数组中对应位置的某一元素,然后通过key的equals方法在对应位置的链表中找到需要的元素.所以,hashcode与equals方法对于找到对应元素是两个关键方法.  Hashmap的key可以是任何类型的对象,例如User这种对象,为了保证两个具有相同属性的user的hashcode相同,我们就需要改写hashcode方法,比方把hashcode值的计算与User对象的id关联起来,那么只要user对象拥有相同id,那么他们的hashcode也能保持一致了,这样就可以找到在hashmap数组中的位置了.如果这个位置上有多个元素,还需要用key的equals方法在对应位置的链表中找到需要的元素,所以只改写了hashcode方法是不够的,equals方法也是需要改写滴~当然啦,按正常思维逻辑,equals方法一般都会根据实际的业务内容来定义,例如根据user对象的id来判断两个user是否相等.  在改写equals方法的时候,需要满足以下三点:  (1) 自反性:就是说a.equals(a)必须为true.  (2) 对称性:就是说a.equals(b)=true的话,b.equals(a)也必须为true.  (3) 传递性:就是说a.equals(b)=true,并且b.equals(c)=true的话,a.equals(c)也必须为true.  通过改写key对象的equals和hashcode方法,我们可以将任意的业务对象作为map的key(前提是你确实有这样的需要).  正确使用HashMap 1:不要在并发场景中使用HashMap HashMap是线程不安全的,如果被多个线程共享的操作,将会引发不可预知的问题,据sun的说法,在扩容时,会引起链表的闭环,在get元素时,就会无限循环,后果是cpu100%.   2:如果数据大小是固定的,那么最好给HashMap设定一个合理的容量值 根据上面的分析,HashMap的初始默认容量是16,默认加载因子是0.75,也就是说,如果采用HashMap的默认构造函数,当增加数据时,数据实际容量超过10*0.75=12时,HashMap就扩容,扩容带来一系列的运算,新建一个是原来容量2倍的数组,对原有元素全部重新哈希,如果你的数据有几千几万个,而用默认的HashMap构造函数,那结果是非常悲剧的,因为HashMap不断扩容,不断哈希,在使用HashMap的场景里,不会是多个线程共享一个HashMap,除非对HashMap包装并同步,由此产生的内存开销和cpu开销在某些情况下可能是致命的. 当创建 HashMap 时,有一个默认的负载因子(load factor),其默认值为 0.75,这是时间和空间成本上一种折衷:增大负载因子可以减少 Hash 表(就是那个 Entry 数组)所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的的操作(HashMap 的 get() 与 put() 方法都要用到查询);减小负载因子会提高数据查询的性能,但会增加 Hash 表所占用的内存空间. 掌握了上面知识之后,我们可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值;如果程序比较关心空间开销、内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕则可以适当的减少负载因子.通常情况下,程序员无需改变负载因子的值. 如果开始就知道 HashMap 会保存多个 key-value 对,可以在创建时就使用较大的初始化容量,如果 HashMap 中 Entry 的数量一直不会超过极限容量(capacity * load factor),HashMap 就无需调用 resize() 方法重新分配 table 数组,从而保证较好的性能.当然,开始就将初始容量设置太高可能会浪费空间(系统需要创建一个长度为 capacity 的 Entry 数组),因此创建 HashMap 时初始化容量设置也需要小心对待.      Fail-Fast机制 HashMap不是线程安全的,因此如果在使用迭代器的过程中有其他线程修改了map,那么将抛出异常,这就是所谓fail-fast策略. 这一策略在源码中的实现是通过modCount域,modCount:修改次数,对HashMap内容的修改都将增加这个值,那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount.在迭代过程中,判断modCount跟expectedModCount是否相等,如果不相等就表示已经有其他线程修改了Map.注意到modCount声明为volatile,保证线程之间修改的可见性. HashIterator() { expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } }  final Entry nextEntry() { if (modCount != expectedModCount) throw new ConcurrentModificationException();   在HashMap的API中指出:由所有HashMap类的"collection 视图方法"所返回的迭代器都是快速失败的:在迭代器创建之后,如果从结构上对映射进行修改,除非通过迭代器本身的 remove 方法,其他任何时间任何方式的修改,迭代器都将抛出ConcurrentModificationException.因此,面对并发的修改,迭代器很快就会完全失败,而不冒在将来不确定的时间发生任意不确定行为的风险. 注意迭代器的快速失败行为不能得到保证,一般来说,存在非同步的并发修改时,不可能作出任何坚决的保证.快速失败迭代器尽最大努力抛出 ConcurrentModificationException.因此,编写依赖于此异常的程序的做法是错误的,正确做法是:迭代器的快速失败行为应该仅用于检测程序错误. 总结: 本文主要描述了HashMap的结构,和hashmap中hash函数的实现,以及该实现的特性,同时描述了hashmap中resize带来性能消耗的根本原因,以及将普通的域模型对象作为key的基本要求.尤其是hash函数的实现,可以说是整个HashMap的精髓所在,只有真正理解了这个hash函数,才可以说对HashMap有了一定的理解. 参考文档 http://www.iteye.com/topic/907293 JDK源代码学习系列一---java.util(2) http://www.iteye.com/topic/754887 HashMap深度分析 http://www.iteye.com/topic/539465 深入理解HashMap http://www.iteye.com/topic/995647 三顾java.util.HashMap http://www.iteye.com/topic/992907 HashMap源码阅读 http://www.iteye.com/topic/1122544 java集合包深入 http://itemdetail.iteye.com/category/121942 集合源码解析 http://zhangshixi.iteye.com/blog/672697 深入Java集合学习系列:HashMap的实现原理 http://java-mzd.iteye.com/blog/827523 Hash表分析以及Java实现 http://blog.csdn.net/turkeyzhou/article/category/365499/2 JDK源代码分析聚集篇 http://www.ibm.com/developerworks/cn/java/j-lo-hash 通过分析 JDK 源代码研究 Hash 存储机制 http://www.ibm.com/developerworks/cn/java/j-lo-tree 通过分析 JDK 源代码研究 TreeMap 红黑树算法实现 http://www.iteye.com/topic/1103980 Java并发编程之ConcurrentHashMap

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 1 人已下载

下载文档