【第286期】面试时被问到Flutter/Dart的HashMap怎么办？

日期：2023-10-05 03:10

前言相信很多同学在面试的时候都被问到过HashMap，特别是对于java/Android程序员来说，HashMap几乎肯定会被提及。因为这里可以探讨的点实在是太多了。关于Java的HashMap的采访在网上随处可见。自然，随着Flutter的流行，后面的面试中也可能会被问到关于Flutter/Dart的HashMap的问题。与其问问题，我们现在来了解一下 Flutter/Dart 的 HashMap。在这篇文章中，关于Dart的HashMap，我首先列出一些面试中可能会遇到的问题，然后根据源码做一些介绍，最后对这些问题给出一个粗略的解答。希望对大家有帮助。 HashMap 和 LinkedHashMap 有什么区别？这个表达式最终map = Map();生成的地图是上面两个地图之一吗？ HashMap的底层数据结构是怎样的？ HashMap的默认大小是多少？ HashMap如何处理哈希冲突？ HashMap什么时候扩容？如何拓展？ LinkedHashMap的底层数据结构是怎样的？ LinkedHashMap如何处理哈希冲突？ LinkedHashMap什么时候扩容？如何拓展？带着这些问题我们看一下源码使用 HashMap 和 LinkedHashMap 创建一个HashMap实例：最终映射 = HashMap(); 创建 LinkedHashMap 实例最终映射 = LinkedHashMap(); 创建一个地图实例最终地图=Map(); 你在这里得到的map实际上是一个LinkedHashMap。其工厂构造函数如下： @patchclass Map { ... @patchfactory Map() => new LinkedHashMap(); ...} 添加/更改地图['一'] = 1; 删除地图.删除('一'); 查看最终值=map['one']; 添加、修改、查看操作与操作数组相同。要删除，需要调用remove()。迭代器最终 it = map.entries.iterator; while(it.moveNext()) { print(it.current); } Dart 语言的一大特点就是极其灵活。这里仅介绍一些常见的操作。其他不同的写法可以参考API文档。接下来我们就深入源码来一探究竟。哈希映射构造函数 @patch class HashMap { @patchfactory HashMap( {bool equals(K key1, K key2)?, int hashCode(K key)?, bool isValidKey(potentialKey)?}) { if (isValidKey == null) { if (hashCode == null) { if (equals == null) { return new _HashMap(); } } ... } HashMap 构造函数有三个可选参数。我们不会在这里传递它们。在这种情况下，将返回一个 _HashMap 实例。如果有输入参数，则返回另外两种类型_IdentityHashMap和_CustomHashMap之一。由于篇幅限制，本文不会对此进行介绍。如果有兴趣可以直接去看源码。底层结构 var _buckets = List<_HashMapEntry?>.filled(_INITIAL_CAPACITY, null); 这看起来像是数组+链表的形式。哈希图.jpg 初始容量：静态常量 int _INITIAL_CAPACITY = 8; 我们知道Java的HashMap初始化大小是16，而Dart使用8。虽然不同，但仍然是2的幂。另外，Dart似乎没有为用户提供自定义初始化大小的机会。点击查看过去的面试问题。查找操作V？运算符 [](Object? key) { 最终 hashCode = key.hashCode;最终桶= _buckets；最终索引 = hashCode & (buckets.length - 1); var 条目 = 桶[索引]; while (entry != null ) { if (hashCode ==entry.hashCode &&entry.key == key) { returnentry.value; } } 条目 = 条目.下一个;返回空值； } 可见，获取数组下标就是直接将key的hashCode与数组长度-1进行AND运算。最终索引 = hashCode & (buckets.length - 1); 然后比较链表元素中存储的哈希值和键，看它们是否相等。如果不相等，则查找下一个链表元素。如果相等，则返回对应的值。这里要注意的是，没有红黑树。所以Dart的HashMap实现其实和jdk1.8之前的实现类似。赋值操作void operator[]=(K key, V value) { 最终 hashCode = key.hashCode;最终桶= _buckets；最终长度=bucket.length；最终索引 = hashCode & (长度 - 1); var 条目 = 存储桶[索引] ; while (entry != null) { if (hashCode ==entry.hashCode &&entry.key == key) {entry.value = value;返回; } 条目 = 条目.下一个; } _addEntry（桶、索引、长度、键、值、hashCode）； } 这个过程其实和数值运算类似。如果键值对存在，则直接赋值。如果不存在，则调用_addEntry()进行新增操作。void _addEntry(List<_HashMapEntry?>buckets, int index, int length, K key, V value, int hashCode) { 最终条目 = new _HashMapEntry(key, value, hashCode, Buckets[index]);桶[索引] = 条目；最终新元素 = _elementCount + 1; _elementCount = newElements; // 如果我们最终得到超过 75% 的非空条目，我们 // 会调整后备存储的大小。 if ((newElements << 2) > ( (长度 << 1) + 长度)) _resize(); _modificationCount = (_modificationCount + 1) & _MODIFICATION_COUNT_MASK; } 这里注意，创建新的_HashMapEntry时，会传入当前数组的entry，即buckets[index]。然后将新条目分配给buckets[index]。桶[索引] = 条目；这里我们可以猜测应该是采用头部插入的方式。另外，每次有添加或删除等操作时，_modificationCount都会递增。当我们遍历HashMap时，如果有这样的操作，就会引发并发修改异常。这就是“快速失败”机制新的运作显然会涉及到扩张的问题。从上面的注释可以看出，当键值对的数量超过数组容量的75%时，即其负载因子为0.75时，就会进行扩容。这一点与Java相同。这75%的计算过程使用位运算和加法代替除法来提高效率，相当于e*4>l*3 -> e/l>3/4 -> e/l>75% 扩张经营void _resize() { 最终 oldBuckets = _buckets;最终oldLength = oldBuckets.length;最终新长度 = 旧长度 << 1;最终 newBuckets = new List<_HashMapEntry?>.filled(newLength, null); for (int i = 0; i < oldLength; i++) { var entry = oldBuckets[i]; while (entry != null) { 最终下一个=www.introzo.com;最终 hashCode = Entry.hashCode;最终索引 = 哈希码 & (newLength - 1); www.introzo.com = newBuckets[索引]; newBuckets[索引] = 条目；条目=下一个； _buckets = newBuckets； } 新扩展数组的长度是原始长度的两倍。最终新长度 = 旧长度 << 1; 我们知道它的初始长度是8，我们可以看到buckets数组的长度永远是2的幂。从旧数组向新数组转移条目的过程我们也可以看出，这个转移过程同样使用了头部插值。关于扩容需要注意的一点是，当键值对的数量超过数组长度的75%时才会发生扩容，而不是当数组占用超过75%时才会发生扩容。这种误解常见于很多讨论Java HashMap的文章中，也出现过。大家需要仔细理解这里的区别。删除操作void _removeEntry(_HashMapEntry条目, _HashMapEntry? previousInBucket, int bucketIndex) { if (previousInBucket == null) { _buckets[bucketIndex] = www.introzo.com; previousInBucket。下一个删除是从链表中删除节点的正常过程。遍历 void forEach(void action(K key, V value)) { 最终标记 = _modificationCount;最终桶= _buckets；最终长度=bucket.length； for (int i = 0; i < length; i++) { var Entry = Bucket[ i]; while (entry != null) { 操作(entry.key,entry.value); if (stamp != _modificationCount) { 抛出新的 ConcurrentModificationError(this); } 条目 = 条目.下一个; 遍历将从数组的第一个位置开始顺序访问链表中的每一项。显然，这种遍历顺序并不能保证与键值对的插入顺序一致。这里我们也可以看到“Fail-Fast”机制生效了。如果用户在遍历过程中对HashMap进行了添加或删除操作，那么stamp和_modificationCount将不相等，从而导致ConcurrentModificationError异常。概括 Dart的HashMap一般实现起来都比较简单。总体来说和jdk1.7版本的HashMap类似。相信学过Java实现的同学会发现dart的HashMap更容易理解。链接哈希映射从API文档来看，LinkedHashMap和HashMap的区别在于LinkedHashMap在遍历时保留了键值对的插入顺序。在jdk中，LinkedHashMap的实现是将Node转化为双向链表以保留顺序。 Dart 的 LinkedHashMap 实现是不同的。构造函数 @patchclass LinkedHashMap { @patchfactory LinkedHashMap( {bool equals(K key1, K key2)?, int hashCode(K key)?, bool isValidKey(potentialKey)?}) { if (isValidKey == nu ll) { if (hashCode == null) { 同样，LinkedHashMap 构造函数具有三个可选输入参数，但我们在这里不传递它们。在这种情况下，将返回一个 _InternalLinkedHashMap 实例。如果有输入参数，则会返回另外两种类型_CompactLinkedIdentityHashMap和_CompactLinkedCustomHashMap中的一种，本文不做介绍。点击查看过去的面试问题。底层结构我们直接看_InternalLinkedHashMap。 _InternalLinkedHashMap 构造函数：_InternalLinkedHashMap() { _index = new Uint32List(_HashBase._INITIAL_INDEX_SIZE); _hashMask = _HashBase._indexSizeToHashMask(_HashBase._INITIAL_INDEX_SIZE); _data = new List.filled(_HashBase._IN ITIAL_INDEX_SIZE, null); _usedData = 0; _deletedKeys = 0; } 可以看到_InternalLinkedHashMap的底层有两个数组，_index和_data。 _index数组以哈希码为下标记录了对应键值对在_data数组中的位置。 _data 数组按插入顺序存储键和值。该图表示如下：无标题图-2.png 两个数组的初始长度都是_INITIAL_INDEX_SIZE。下面的代码显示它的值为16。_data数组存储的是键值对，最多只能存储8个键值对。也就是说，LinkedHashMap的初始容量实际上是8。抽象类 _HashBase 实现 _HashVMBase { ... static const int _INITIAL_INDEX_BITS = 3;静态常量 int _INITIAL_INDEX_SIZE = 1 << (_INITIAL_INDEX_BITS + 1); } LinkedHashMap底层实际上是采用线性检测的方法来实现的。数组_index中存储的是一个称为pair的整数。之所以称为pair，是因为它由高位和低位两部分组成。高位称为hashPattern，低位称为entry。 Entry指向_data数组对应的键值对。从hashcode到真正的键值对的查找过程中的关键点其实就是这个entry。同时，pair还用来表示_index数组中对应位置的状态。 0（_UNUSED_PAIR）表示当前未使用，1（_DELETED_PAIR）表示当前位置处于删除状态：抽象类 _HashBase 实现 _HashVMBase { ... static const int _UNUSED_PAIR = 0;静态常量 int _DELETED_PAIR = 1; ...} 屏幕截图 2021-05-21 12.16.13 AM.png 查找操作 V？运算符 [](Object? key) { var v = _getValueOrData(key);返回相同的（_data，v）？ null : 内部.unsafeCast(v); } 搜索最终会调用_getValueOrData目的？ _getValueOrData(Object? key) { 最终 int 大小 = _index.length;最终 int sizeMask = 大小 - 1;最终 int maxEntries = 大小 >> 1;最终 int fullHash = _hashCode(key);最终 int hashPattern = _HashBase._h ashPattern(fullHash, _hashMask, 大小); int i = _HashBase._firstProbe(fullHash, sizeMask); int 对 = _index[i]; while (pair != _HashBase._UNUSED_PAIR) { if (pair != _HashBase._DELETED_PAIR) { 最终 int 条目 = hashPattern ^pair; if (entry < maxEntries) { 最终 int d =entry << 1; if (_equals(key, _data[d])) { return _data[d + 1]; }由于 _nextProbe(i, sizeMask);对 = _index[i];返回_数据； } 从这个函数我们可以理解线性检测的过程。首先通过调用_HashBase._firstProbe()获取首地址：静态 int _firstProbe(int fullHash, int sizeMask) { 最终 int i = fullHash & sizeMask; // 轻量、快速的洗牌以减轻错误的 hashCode（例如，顺序的）。返回 ((i << 1) + i) & sizeMask; } 第一个检测是取哈希码和数组长度的模。注意还有一步，就是将 i 乘以 3，然后取模。从评论来看，是为了让hashcode分布更加均匀。你可以想想原因。第一次检测后，就获得了该对。如果该pair没有被占用，则说明该键值对不存在，按照约定直接返回_data数组。如果是已删除状态，则进行第二次检测。如果处于正常占用状态，则将该pair与hashPattern进行异或。从上图可以看出，获取到了条目。如果检查条目没有越界，则将其乘以 2 以获取键在 _data 数组中的位置。最后，如果判断key相等，则返回_data的下一个元素，即value。二次检测会调用_HashBase._nextProbe() 静态 int _nextProbe(int i, int sizeMask) => (i + 1) & sizeMask; 源码可见，下一个地址一一尝试就可以了。赋值操作void operator[]=(K key, V value) { Final int size = _index.length;最终 int fullHash = _hashCode(key);最终 int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, 大小);最终 int d = _findValueOrInsert Point(key, fullHash, hashPattern, size); if (d > 0) { _data[d] = 值; } else { 最终 int i = -d; _insert(键、值、hashPattern、i); } } 赋值时，会首先调用_findValueOrInsertPoint()来查找现有的键值对。其逻辑与函数_getValueOrData类似。如果键值对存在，则直接返回_data中对应值的位置，然后直接赋值。如果不存在，则返回负数。这个负数实际上就是检测后_index数组中可用的位置。有了这个位置，就可以调用_insert()来执行插入操作了。 void _insert(K key, V value, int hashPattern, int i) { if (_usedData == _data.length) { _rehash(); }这个[键] = 值； } else { 断言(1 <= hashPattern && hashPattern < (1 << 32)); final int index = _usedData >> 1; 断言 t ((index & hashPattern) == 0); _index[i] = hashPattern | index; _data[_usedData++] = key; _data[_usedData++] = value; } }插入前先检查_data数组是否已满。如果满了，必须调用_rehash()来扩容。如果未满，就是简单的赋值操作。将_data的下一个空位置除以2并与hashPattern进行OR运算，然后放入_index数组中，然后将相邻的key和value放入_data数组中。扩张经营 void _rehash() { if ((_deletedKeys << 2) > _usedData) { _init(_index.length, _hashMask, _data, _usedData); } else { _init(_index.length << 1, _hashMask >> 1, _data, _usedData ); } } 在扩展之前，首先检查数组中是否有超过一半的元素处于删除状态。如果是这样，则扩展后的长度与原始数组长度相同。否则，新数组的长度将是原始长度的两倍。为什么这有效？让我们看一下 _init() 函数。 void _init(int size, int hashMask, List? oldData, int oldUsed) { _index = new Uint32List(size); _hashMask = 哈希掩码； _data = new List.filled(size, null); _usedData = 0; _deletedKeys = 0; if (oldData != null) { for (int i = 0; i < oldUsed; i += 2) { var key = oldData[i]; } if (!_HashBase._isDeleted(oldData, key)) { this[key] = oldData[i + 1]; 这里，_index和_data数组将根据新的长度创建。然后将制作一份副本。如果键值对处于删除状态，则不会被复制。因此，与原数组一样长的“扩容”过程实际上意味着删除的元素实际上被删除了。删除操作V？删除（对象？键）{ 最终int大小= _index.length;最终 int sizeMask = size - 1;最终 int maxEntries = 大小 >> 1;最终 int fullHash = _hashCode(key);最终 int hashPattern = _HashBase._hashPattern(fullHash, _hashMask, size); int i = _HashBase._firstProbe(fullHash, sizeMask); intpair = _index[i]; while (pair != _HashBase._UNUSED_PAIR) { if (pair != _HashBase._DELETED_PAIR) { 最终 in entry = hashPattern ^ pair; if (entry < maxEntries){ final int d =entry << 1; if (_equals(key, _data[d])) { _index[i] = _HashBase._DELETED_PAIR; _HashBase._setDeletedAt(_data, d); V值=_data[d+1]； _HashBase._setDeletedAt(_data, d + 1); ++_deletedKeys；返回值； } } } i = _HashBase._nextProbe(i, sizeMask);对 = _index[i]; } 返回 null； }删除过程也是首先进行线性检测。如果找到它，请做两件事。首先将_index数组对应的位置设置为_HashBase._DELETED_PAIR。然后将_data数组对应的位置设置为_data。遍历我们知道LinkedHashMap会保证遍历顺序和插入顺序相同。通过上面的介绍，我们知道插入的键值对是按顺序存储在_data数组中的。那么遍历的时候只需要遍历_data数组，自然就按照插入顺序遍历LinkedHashMap了。 bool moveNext() { if (_table._isModifiedSince(_data, _checkSum)) { 抛出新的 ConcurrentModificationError(_table); } } 执行 { _offset += _step; } while (_offset < _len && _HashBase._isDeleted(_data, _data[_offset])); if (_offset < _len) { _current = internal.unsafeCast(_data[_offset ]); 返回 true; } else { _current = null; 返回 false; } } 如果删除该键值对，则会跳过该键值对。概括 Dart的LinkedHashMap实现与jdk的不同。当你第一次接触它时，你可能会感到陌生。需要仔细研究源码才能看到具体的实现，也能学到一些东西。总结总体来说，Dart的HashMap和LinkedHashMap的实现比较简单，没有像jdk那样进行详细的优化工作。这可能需要 Dart/Flutter 进一步开发。但我们也可以看到，无论是什么语言，一些基本数据结构的设计思想是相同的。点击查看过去的面试问题。一旦掌握了源代码背后的设计思想，就可以举一反三。无论是哪种新语言、新架构，你都可以快速掌握。最后，我将把前几个问题和粗略的答案放在一起： HashMap 和 LinkedHashMap 有什么区别？从API角度来看，HashMap不保证遍历顺序与插入顺序相同，而LinkedHashMap则保证遍历顺序与插入顺序相同。这个表达式最终map = Map();生成的地图是上面两个地图之一吗？是一个LinkedHashMap。 HashMap的底层数据结构是怎样的？数组+链表。 HashMap的默认大小是多少？ 8. HashMap如何处理哈希冲突？链地址法。 HashMap什么时候扩容？如何拓展？当键值对的数量超过数组长度的75%时才会发生扩容，而不是当数组占用超过75%时才会发生扩容。扩容后的新数组长度将是原数组长度的两倍，扩容过程采用头插入方式。 LinkedHashMap的底层数据结构是怎样的？两个数组：_index 和 _data。 _index数组以哈希码为下标，记录对应键值对在_data数组中的位置。 _data 数组按插入顺序存储键和值。 LinkedHashMap如何处理哈希冲突？线性检测方法。 LinkedHashMap什么时候扩容？如何拓展？ _data 数组满时会扩展。在扩容之前，首先检查数组中是否有超过一半的元素处于删除状态。如果是这样，则扩展长度与原始数组长度相同。否则，新数组长度是原始长度的两倍。

最近发表

猜你喜欢

【第286期】面试时被问到Flutter/Dart的HashMap怎么办？

相关文章