2023年6月27日发(作者：)

Android⾯试之HashMap的实现原理AndroidDeveloper 2016-11-10 15:40读完本⽂需要10分钟每天弄清⼀个点，轻松搞定android⾯试精诚所⾄，⾦⽯为开建议看到问题后，先⾃⼰想想能不能完整说出来，然后再看后⾯答案。今天的⾯试话题是：HashMap的实现原理1、HashMap与HashTable的区别HashMap允许key和value为null；HashMap是⾮同步的，线程不安全，也可以通过onizedMap()⽅法来得到⼀个同步的HashMapHashMap存取速度更快，效率⾼HashMap去掉了HashTable中的contains⽅法，加上了containsValue和containsKey⽅法2、HashMap的实现原理⼀句话理解HashMap：HashMap就是Hash表的Map实现。 Hash表就是Hash数组，Map实现是指实现了Map接⼝。1. HashMap的数据结构HashMap的底层是基于数组和链表实现的，存储速度快的原因是因为它是通过计算散列码来决定存储的位置。HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就⼀样。如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。解决hash冲突的⽅法有很多，HashMap底层是通过链表来解决hash冲突的。HashMap中Entry类源码static class Entry implements {final K key;V value;Entry next;final int hash;Entry(int h, K k, V v, Entry 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;}public final boolean equals(Object o) {if (!(o instanceof ))return false; e = ()o;Object k1 = getKey();Object k2 = ();if (k1 == k2 || (k1 != null && (k2))) {Object v1 = getValue();Object v2 = ue();if (v1 == v2 || (v1 != null && (v2)))return true;}return false;}public final int hashCode() {return (key==null ? 0 : de()) ^(value==null ? 0 : de());}public final String toString() {return getKey() + "=" + getValue();}void recordAccess(HashMap m) {}void recordRemoval(HashMap m) {}}HashMap其实就是⼀个Entry数组，Entry对象中包含了键和值，其中next也是⼀个Entry对象，它就是⽤来处理hash冲突的，形成⼀个链表。2. HashMap的⼏个变量transient Entry[] table;//存储Entry的数组transient int size;//存放entry的个数int threshold;//下限，临界值，数组长度超过这个值会扩容，threshold = loadFactor*容量；final float loadFactory；//加载因⼦，加载因⼦越⼤表⽰当前数组填满的元素越多，空间利⽤率⾼，不⽅便查询；加载因⼦越⼩，表⽰填满元素越少，空间利⽤率低，⽅便速度快。默认值是0.75；transient int modCount；//被修改的次数3. 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 || (loadFactor)) throw newIllegalArgumentException("Illegal load factor: " +loadFactor); // Find a power of 2 >= initialCapacityint capacity = 1;while (capacity < initialCapacity)capacity <<= 1; ctor = loadFactor;threshold = (int)(capacity * loadFactor);table = new Entry[capacity];init();}允许我们⾃⼰指定初始容量和加载因⼦public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}只指定初始容量，加载因⼦使⽤默认的0.75；public HashMap() { ctor = DEFAULT_LOAD_FACTOR;threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);table = new Entry[DEFAULT_INITIAL_CAPACITY];init();}初始容量和加载因⼦全部使⽤默认的值，默认初始的加载容量是16，加载因⼦是0.75；4. 存储数据put⽅法public V put(K key, V value) {if (key == null)return putForNullKey(value);int hash = hash(de());int i = indexFor(hash, );for (Entry e = table[i]; e != null; e = ) {Object k; if ( == hash && ((k = ) == key || (k))) {V oldValue = ; = value;Access(this); return oldValue;}}modCount++;addEntry(hash, key, value, i); return null;}可以看出，HashMap存放数据的时候，会先拿到key的hashCode值，对其进⾏hash运算，得到具体的hash值，然后根据hash值查找存放的位置，找到存放的位置后，然后遍历table数组找到对应位置的entry，如果当前的key已经存在，且对⽐entry的hash值和key相同的话，那么就更新value值；否则就将key和value值加到数组中；这⾥需要注意：判断是否2个Entry相同，需要从2⽅⾯判断：1、2个Entry的key必须相同（k = ||(k)）；2、2个Entry的hashCode，也就是hash值必须相同（这⾥说的hash是经过hash（hashCode）换算后的值）；上述2个条件都满⾜的话，才可以认定当前Entry已经存在，新的Entry才会替换旧的Entry。下⾯给出put过程中，涉及到的2个⽅法- 根据hashCode求hash码的实现static int hash(int h) {h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}- 根据hash码求存储在数组中的索引static int indexFor(int h, int length) { //根据hash值和数组长度算出索引值2 return h & (length-1); //这⾥不能随便算取，⽤hash&(length-1)是有原因的，这样可以确保算出来的索引是在数组⼤⼩范围内，不会超出3 }这⾥有些同学会好奇，为什么索引值是h & (length-1)？ 其实，这⾥⾯的故事还是挺多的。 ⼀般对哈希表求散列我们会使⽤hash值对length取模，HashTable就是这样实现的，这种⽅法可以保证元素在哈希表中散列均匀，但取模会⽤到除法运算，效率⾮常低，HashMap是对HashTable进⾏改进后的实现，为了提⾼效率，使⽤h&（length-1）取代除法运算，在保证散列均匀的基础上还保持了效率的提升。5. resize⽅法⽤于重新扩⼤缩⼩数组的⼤⼩void resize(int newCapacity) {Entry[] oldTable = table;int oldCapacity = ;if (oldCapacity == MAXIMUM_CAPACITY) {threshold = _VALUE;return;}Entry[] newTable = new Entry[newCapacity];transfer(newTable);table = newTable;threshold = (int)(newCapacity * loadFactor);}其实就是新建⼀个⼤的数组，把原来的数据重新添加进去。什么时候才会触发resize⽅法呢？当当前元素的数量达到数组总size的loadFactor（默认0.75）时候，会调⽤resize⽅法，将数组扩⼤为原来⼤⼩的2倍；6. HashMap的get⽅法public V get(Object key) {if (key == null)return getForNullKey();int hash = hash(de());for (Entry e = table[indexFor(hash, )];e != null;e = ) {Object k;if ( == hash && ((k = ) == key || (k)))return ;}return null;}可以看出，⾸先拿到key的hashcode，求出hash码，根据hash码找到索引的位置，然后去数组中获取对应索引的元素，如果key的hash相同，key相同的话，那么这就是我们要找的entry，把entry的值返回出去就Ok了。如果⼤家觉得好，⼤家转载的同时，也点点⽂章最下⾯“AndroidDeveloper”的订阅按钮，关注“AndroidDeveloper”