Guava学习之HashBiMap

最后更新于:2022-04-01 14:16:15

[HashBiMap](http://www.iteblog.com/archives/tag/hashbimap "查看 HashBiMap 中的全部文章")存储的键和值都只能唯一,不存在键与键、值与值相同的情况(详细分析见我博客:[Guava学习之BiMap](http://www.iteblog.com/archives/501 "Guava学习之BiMap"))。[HashBiMap](http://www.iteblog.com/archives/tag/hashbimap "查看 HashBiMap 中的全部文章")类继承了AbstractMap类并实现了BiMap接口,其类继承关系如下图所示: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-05-17_573adb4063de0.jpg) HashBiMap AbstractMap类实现了Map接口定义的一些方法,而BiMap类定义了其子类需要实现的一些方法,使得所有实现BiMap的类必须符合其独有的特性:键、值都是唯一的。[HashBiMap](http://www.iteblog.com/archives/tag/hashbimap "查看 HashBiMap 中的全部文章")类中主要有以下几个成员变量: ~~~ private static final double LOAD_FACTOR = 1.0; private transient BiEntry<K, V>[] hashTableKToV; private transient BiEntry<K, V>[] hashTableVToK; private transient int size; private transient int mask; private transient int modCount; ~~~ LOAD_FACTOR是承载因子,这里等于1,而我们熟悉的HashMap承载因子为0.75。LOAD_FACTOR关系到当容器中元素的个数达到了总容量的多少就得分配新的空间。hashTableKToV和hashTableVToK分别存储类型为BiEntry的键值对,都是存储键->值对的,但是目的不一样。size是HashBiMap中元素的个数;mask在求元素的hash值有用。HashBiMap类提供了以下三个静态函数来构造一个HashBiMap: ~~~ public static <K, V> HashBiMap<K, V> create() { return create(16); } public static <K, V> HashBiMap<K, V> create(int expectedSize) { return new HashBiMap<K, V>(expectedSize); } public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) { HashBiMap<K, V> bimap = create(map.size()); bimap.putAll(map); return bimap; } ~~~ HashBiMap默认容量为16,当用户自己决定容器大小(expectedSize)的时候,它是利用以下算法来分配容量的: ~~~ private HashBiMap(int expectedSize) { init(expectedSize); } private void init(int expectedSize) { checkArgument(expectedSize >= 0, "expectedSize must be >= 0 but was %s", expectedSize); int tableSize = Hashing.closedTableSize(expectedSize, LOAD_FACTOR); this.hashTableKToV = createTable(tableSize); this.hashTableVToK = createTable(tableSize); this.mask = tableSize - 1; this.modCount = 0; this.size = 0; } static int closedTableSize(int expectedEntries, double loadFactor) { // Get the recommended table size. // Round down to the nearest power of 2. expectedEntries = Math.max(expectedEntries, 2); int tableSize = Integer.highestOneBit(expectedEntries); // Check to make sure that we will not exceed the maximum load factor. if (expectedEntries > (int) (loadFactor * tableSize)) { tableSize <<= 1; return (tableSize > 0) ? tableSize : MAX_TABLE_SIZE; } return tableSize; } public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); } ~~~ 可以看出,算法分配的容量一定是2的幂数。从内部实现,可以知道,HashBiMap是利用hashTableKToV和hashTableVToK数组作为hash映射的,利用key求得的Hash值是映射到hashTableKToV数组中的,而利用value求得的hash值是映射到hashTableVToK数组中的,为什么需要两个数组分别映射key和value呢?因为BiMap可以将键值反转,也就是键变成值,值变成键。利用下面的结构就方便了这样的操作,如下图所示: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-05-17_573adb4085d37.jpg) HashBiMap结构 其中方框是hash的桶,用于hash映射,同时也可以存储元素;而圆点代表的是节点,里面存储的是BiEntry类型的键值对,也就是HashBiMap的数据,元素与元素之间是通过指针链接的,同一Hash值的元素按照元素出现的先后顺序映射到同一个桶中。而且hashTableKToV和hashTableVToK数组中的元素个数、类型以及数据一定是一致的,只是映射的地方不一致,因为分别以key和velue做影射的。最后一个节点指向的元素为null,这样方便算法中循环终止的判断。 下面介绍了HashBiMap插入元素的实现步骤: 假如有entry6元素(下图中的蓝色圆圈)需要插入到HaspBiMap中: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-05-17_573adb40a9de6.jpg) HashBiMap 首先,我们需要求得entry6的key的hash值,假如entry6元素key求得的hash值为4,这样就需要将它插入到hashTableKToV下标为4的地方,算法如下: ~~~ int keyBucket = entry.keyHash & mask; entry.nextInKToVBucket = hashTableKToV[keyBucket]; hashTableKToV[keyBucket] = entry; ~~~ 具体过程见下: ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-05-17_573adb40c544a.jpg) HashBiMap插入元素 ![](https://docs.gechiui.com/gc-content/uploads/sites/kancloud/2016-05-17_573adb40df738.jpg) HashBiMap插入元素 插完之后的图如上图所示,这样就完成了利用key求hash值然后插入到hashTableKToV中的实现,其实我们还需要求按照value求hash然后将entry6插入到hashTableVToK相应位置上去,不过实现算法和这个一样,就不说了。元素的删除也和这个类似,就不做介绍了。 需要注意:插入元素到hashTableKToV中,就会发生容量溢出的问题,HashBiMap是利用下面算法实现的:   1、判断HashBiMap容器中元素的个数是否大于承载因子乘以hashTableKToV的大小,也即size > loadFactor * tableSize && tableSize < MAX_TABLE_SIZE;   2、如果是,就将当前hashTableKToV和hashTableVToK的大小扩大为tableSize * 2,之后将原来hashTableKToV和hashTableVToK中的元素分别按照新的数组大小再一次映射到扩容后的hashTableKToV和hashTableVToK中去。 实现代码如下: ~~~ private void rehashIfNecessary() { BiEntry<K, V>[] oldKToV = hashTableKToV; if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) { int newTableSize = oldKToV.length * 2; this.hashTableKToV = createTable(newTableSize); this.hashTableVToK = createTable(newTableSize); this.mask = newTableSize – 1; this.size = 0; for (int bucket = 0; bucket < oldKToV.length; bucket++) { BiEntry<K, V> entry = oldKToV[bucket]; while (entry != null) { BiEntry<K, V> nextEntry = entry.nextInKToVBucket; insert(entry); entry = nextEntry; } } this.modCount++; } } static boolean needsResizing(int size, int tableSize, double loadFactor) { return size > loadFactor * tableSize && tableSize < MAX_TABLE_SIZE; } ~~~ 这些操作对应外面的用户是完全透明的,完全不需要用户知道。当然,如果你事先知道需要放入HashBiMap中的元素个数,最好利用create(int expectedSize)来构造一个HaspBiMap,这样可以减少重新分配容量带来的开销。(完) **转载请注明: 转载自[过往记忆(http://www.iteblog.com/)](http://www.iteblog.com/) 本文链接地址: [Guava学习之HashBiMap(http://www.iteblog.com/archives/704)](http://www.iteblog.com/archives/704)**
';