Java集合面试题汇总篇 (4)

initialCapacity:初始容量。指的是 HashMap 集合初始化的时候自身的容量。可以在构造方法中指定;如果不指定的话,总容量默认值是 16 。需要注意的是初始容量必须是 2 的幂次方。(1.7中,已知HashMap中将要存放的KV个数的时候,设置一个合理的初始化容量可以有效的提高性能

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

size:当前 HashMap 中已经存储着的键值对数量,即 HashMap.size() 。

loadFactor:加载因子。所谓的加载因子就是 HashMap (当前的容量/总容量) 到达一定值的时候,HashMap 会实施扩容。加载因子也可以通过构造方法中指定,默认的值是 0.75 。举个例子,假设有一个 HashMap 的初始容量为 16 ,那么扩容的阀值就是 0.75 * 16 = 12 。也就是说,在你打算存入第 13 个值的时候,HashMap 会先执行扩容。

threshold:扩容阀值。即 扩容阀值 = HashMap 总容量 * 加载因子。当前 HashMap 的容量大于或等于扩容阀值的时候就会去执行扩容。扩容的容量为当前 HashMap 总容量的两倍。比如,当前 HashMap 的总容量为 16 ,那么扩容之后为 32 。

table:Entry 数组。我们都知道 HashMap 内部存储 key/value 是通过 Entry 这个介质来实现的。而 table 就是 Entry 数组。

JDK1.7 实现

JDK1.7 中 HashMap 由 数组+链表 组成(“链表散列” 即数组和链表的结合体),数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的(HashMap 采用 “拉链法也就是链地址法” 解决冲突),如果定位到的数组位置不含链表(当前 entry 的 next 指向 null ),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度依然为 O(1),因为最新的 Entry 会插入链表头部,即需要简单改变引用链即可,而对于查找操作来讲,此时就需要遍历链表,然后通过 key 对象的 equals 方法逐一比对查找。

所谓 “拉链法” 就是将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

Java集合面试题汇总篇

源码解析 构造方法

《阿里巴巴 Java 开发手册》推荐集合初始化时,指定集合初始值大小。(说明:HashMap 使用HashMap(int initialCapacity) 初始化)建议原因: https://www.zhihu.com/question/314006228/answer/611170521

// 默认的构造方法使用的都是默认的初始容量和加载因子 // DEFAULT_INITIAL_CAPACITY = 16,DEFAULT_LOAD_FACTOR = 0.75f public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } // 可以指定初始容量,并且使用默认的加载因子 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } 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); // 设置加载因子 this.loadFactor = loadFactor; threshold = initialCapacity; // 空方法 init(); } public HashMap(Map<? extends K, ? extends V> m) { this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); inflateTable(threshold); putAllForCreate(m); }

HashMap 的前 3 个构造方法最后都会去调用 HashMap(int initialCapacity, float loadFactor) 。在其内部去设置初始容量和加载因子。而最后的 init() 是空方法,主要给子类实现,比如LinkedHashMap。

put() 方法 public V put(K key, V value) { // 如果 table 数组为空时先创建数组,并且设置扩容阀值 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 如果 key 为空时,调用 putForNullKey 方法特殊处理 if (key == null) return putForNullKey(value); // 计算 key 的哈希值 int hash = hash(key); // 根据计算出来的哈希值和当前数组的长度计算在数组中的索引 int i = indexFor(hash, table.length); // 先遍历该数组索引下的整条链表 // 如果该 key 之前已经在 HashMap 中存储了的话,直接替换对应的 value 值即可 for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; //先判断hash值是否一样,如果一样,再判断key是否一样,不同对象的hash值可能一样 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; // 如果该 key 之前没有被存储过,那么就进入 addEntry 方法 addEntry(hash, key, value, i); return null; } void addEntry(int hash, K key, V value, int bucketIndex) { // 当前容量大于或等于扩容阀值的时候,会执行扩容 if ((size >= threshold) && (null != table[bucketIndex])) { // 扩容为原来容量的两倍 resize(2 * table.length); // 重新计算哈希值 hash = (null != key) ? hash(key) : 0; // 重新得到在新数组中的索引 bucketIndex = indexFor(hash, table.length); } // 创建节点 createEntry(hash, key, value, bucketIndex); } //扩容,创建了一个新的数组,然后把数据全部复制过去,再把新数组的引用赋给 table void resize(int newCapacity) { Entry[] oldTable = table; //引用扩容前的Entry数组 int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { //扩容前的数组大小如果已经达到最大(2^30)了 threshold = Integer.MAX_VALUE; //修改阈值为int的最大值(2^31-1),这样以后就不会扩容了 return; } // 创建新的 entry 数组 Entry[] newTable = new Entry[newCapacity]; // 将旧 entry 数组中的数据复制到新 entry 数组中 transfer(newTable, initHashSeedAsNeeded(newCapacity)); // 将新数组的引用赋给 table table = newTable; // 计算新的扩容阀值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); } void transfer(Entry[] newTable) { Entry[] src = table; //src引用了旧的Entry数组 int newCapacity = newTable.length; for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组 Entry<K,V> e = src[j]; //取得旧Entry数组的每个元素 if (e != null) { src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象) do { Entry<K,V> next = e.next; int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置 e.next = newTable[i]; //标记[1] newTable[i] = e; //将元素放在数组上 e = next; //访问下一个Entry链上的元素 } while (e != null); } } } void createEntry(int hash, K key, V value, int bucketIndex) { // 取出table中下标为bucketIndex的Entry Entry<K,V> e = table[bucketIndex]; // 利用key、value来构建新的Entry // 并且之前存放在table[bucketIndex]处的Entry作为新Entry的next // 把新创建的Entry放到table[bucketIndex]位置 table[bucketIndex] = new Entry<>(hash, key, value, e); // 当前 HashMap 的容量加 1 size++; }

最后的 createEntry() 方法就说明了当hash冲突时,采用的拉链法来解决hash冲突的,并且是把新元素是插入到单边表的表头。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zyssfz.html