[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接口,其類繼承關系如下圖所示:

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可以將鍵值反轉,也就是鍵變成值,值變成鍵。利用下面的結構就方便了這樣的操作,如下圖所示:

HashBiMap結構
其中方框是hash的桶,用于hash映射,同時也可以存儲元素;而圓點代表的是節點,里面存儲的是BiEntry類型的鍵值對,也就是HashBiMap的數據,元素與元素之間是通過指針鏈接的,同一Hash值的元素按照元素出現的先后順序映射到同一個桶中。而且hashTableKToV和hashTableVToK數組中的元素個數、類型以及數據一定是一致的,只是映射的地方不一致,因為分別以key和velue做影射的。最后一個節點指向的元素為null,這樣方便算法中循環終止的判斷。
下面介紹了HashBiMap插入元素的實現步驟:
假如有entry6元素(下圖中的藍色圓圈)需要插入到HaspBiMap中:

HashBiMap
首先,我們需要求得entry6的key的hash值,假如entry6元素key求得的hash值為4,這樣就需要將它插入到hashTableKToV下標為4的地方,算法如下:
~~~
int keyBucket = entry.keyHash & mask;
entry.nextInKToVBucket = hashTableKToV[keyBucket];
hashTableKToV[keyBucket] = entry;
~~~
具體過程見下:

HashBiMap插入元素

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)**