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