Java - How to implement basic HashMap by hashing, chaining

簡單說，當我們利用Java提供的HashMap可以實作出key => value對應的關係，而且它的

效率很高，號稱O(1)耶！！，簡直就像一個array，若字串"Ben"在array[500]的address，假設

你知道array[500] => "Ben" (鬼才會去記它在哪XD)，也是O(1)。但若你事先不知道，就一定要

利用迴圈走訪了，此時O(n) (array length)，才有可能得到"Ben"的值，關鍵在於沒有關鍵的key

阿！由於array只能存integer，因此我們可以透過hash function幫我們計算出hash table存放Entry

(組成key and value)的位置，如此一來以後只要將key轉換成table的index，就可以快速查詢到

value囉！

請見下圖(來源: wiki)：

圖一

不過，世事難料，有些key在經由hash function的轉換，會得到相同的index，此時若是key也相

等，很簡單就覆蓋掉舊的值，但若是不同的該怎麼辦？總不能不管他吧？因此可以透過

chaining的方式，就大家很熟悉的link list來做個串接，如下圖(來源: wiki)：

圖二

如此一來，就算是index相同，也可以保留第二筆資料，不過，以後您若是想得到一個

index內的某筆資料，可不是table當下所存的object address就是你要的，還必須去檢查這

個object的key是否與你所要搜尋的key是相等的，意思就是還是要走訪這個object，直到它指

向null為止！

如圖二：若我要搜尋Sandra Dee所對應的value，經由hash function計算得到index = 152，但此

時buckets 152 address存放的entry為John Smith，所以key不相等，就必須走訪至他所串接的下

一筆資料(由於它的下一筆不指向null)，這時才會得到我們要的！

因此，當我們在使用Java提供的HashMap，其實它的內部也做了這些基本的功能，包括

hash function去找index、及chaining Entry等，但其實還包括transfer (若table在使用上超過了原本

預設的size，程式還可以自動擴充table！)。這裡只會舉很簡單的put(K k, V v)、get(Object o)

、remove(Object Key)等基本的method！

接下來的部分，會從HashMap source code獨立出來的幾個method做說明，主要的概念與做

法主要源自於source code，非本人所自創orz...

1. define MyMapEntry class

在MyHashMap class內我會定義這個內部類別，這個類別的意義就是建立一個Entry，表示

key與value所組成的基本原件！，如下：

class MyMapEntry<K, V> implements Map.Entry<K, V>{
   int hash;
   K key;
   V value;
   MyMapEntry<K, V> next;

   public MyMapEntry(int h, K k, V v, MyMapEntry<K, V> n){
      hash = h;
      key = k;
      value = v;
      next = n;
   }

   @Override
   public K getKey() {
      // TODO Auto-generated method stub
      return key;
   }

   @Override
   public V getValue() {
      // TODO Auto-generated method stub
      return value;
   }

   @Override
   public V setValue(V newValue) {
      // TODO Auto-generated method stub
      V oldValue = value;
      value = newValue;
      return oldValue;
   }

   public String toString() {
      return getKey() + " => "+getValue();
   }
}

基本上，這個類別所產生的物件實體會assign到table對應的位置，並且也定義了成員變數next

，來作為當有多個Entry皆存在於同一個table的位置時，可做一個Entry object串接另一個Entry

object的紀錄！(若只有一個Entry，則next指到null)

2. define MyHashMap class

這個類別為外部類別使用的窗口，如同HashMap class，如下：

class MyHashMap<K, V>{
 
   private MyMapEntry<K, V> tables[];
 
   private final int DEFAULT_OPACITY = 16;
 
   @SuppressWarnings("unchecked")
   public MyHashMap(){
      tables = new MyMapEntry[DEFAULT_OPACITY];
   }
   ...
}

當你new MyHashMap後，此時會建立一個MyHashMap型態的tables陣列，預設長度為16！

3. add an Entry

假設在某個外部類別，您要使用MyHashMap，你得先定義您的key, value型態

String str1 = "123";
String str2 = "321";
MyHashMap<String, Integer> map = new MyHashMap<String, Integer>();
map.put(str1, 10);
map.put(str2, 100);

當您呼叫put method，傳進key, value值，此時put method內會先呼叫indexFor及createEntry，

如下：

private int indexFor(int hash, int len){
   return hash & (len - 1);
}

public V put(K k, V v){
   int hash = k.hashCode();
   int i = indexFor(hash, tables.length);
   System.out.println("put key="+k+", value="+v);
   if(tables[i] != null){
      System.out.println("table["+i+"] != null, Filter old key and new key are same?");
      for(MyMapEntry<K, V> e = tables[i]; e != null ; e = e.next){
         if(e.hash == hash && (k.equals(e.key))){
            System.out.println("Old key and new key are same! Override old key's value");
            V oldValue = e.value;
            e.setValue(v);
            return oldValue;
         }
      }
      System.out.println("Old key and new key are different!");
  }
  System.out.println("Create new Entry, and assign to table["+i+"]");
  createEntry(hash, k, v, i);
  return null;
}

private void createEntry(int h, K k, V v, int index){
    MyMapEntry<K, V> entry = tables[index];
    tables[index] = new MyMapEntry<K, V>(h, k, v, entry);
    System.out.println("Prepend new Entry("+k+") to current Entry("+entry+")");
}

首先，它會先將key轉換成hashCode，hashCode如何計算？

假設目前傳進去的key="123"，套用Java hashCode method的計算公式為

h = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] //s[] 字元陣列, n 陣列長度

字元'1' => ascii code為49，以此類推2 => 50 ...

那麼換算後"123"的 h = 48690, 二進位為1011 1110 0011 00102

此時呼叫indexFor method，將hash value與table length-1 (15)做AND運算，如下

1011 1110 0011 0010
& 0000 0000 0000 1111

----------------------------------

0000 0000 0000 0010 => 十進位為2

得到的tables index = 2，表示這個key, value組成的Entry將assign to tables[2]

再來檢查此時的tables[2]是否指向null (default initialize value)

由於是第一筆(肯定為null)，接下來就再去呼叫createEntry method

首先宣告的entry變數會先取得現階段tables[2] 指向的位址，以當作new MyMapEntry所指向

的目標，如此一來，假設有第二個Entry剛好也是在tables[2]，它將會是在前頭，第一個

Entry會在它的後頭，表示越慢進來的在越前面！

再來又put第二筆，key = "321"

換算後得到 h = 50610, 二進位為1100 0101 1011 00102

此時呼叫indexFor method進行運算

1100 0101 1011 0010
& 0000 0000 0000 1111

----------------------------------

0000 0000 0000 0010 => 十進位為2

再來的第二筆data，index也是2，此時tables[2]已不是指向null了，這時就會發生碰撞的問題

，總不能將已有的Entry給取代掉，因此會進入if 內，進行tables[2]下所擁有的Entry走訪

for(MyMapEntry<K, V> e = tables[i]; e != null ; e = e.next){ ... }

假設取得的key與現有的key不僅hash相等，同時內容本身也相等，那麼新的key對應的value

會做覆蓋舊value的動作! 否則，就像前面一樣去呼叫createEntry method！

一樣地，先取得現有的Entry (非null)，帶進new MyHashEntry內，此時新的Entry's next變數會

指向舊的Entry reference address。

此時key - "321"如同圖二的"John Smith"，而key - "123"如同圖二的"Sandra Dee"

4. get mapping value by key

這邊要說明的是如何取得某個key對應的值。

public V get(Object key){
   int hash = key.hashCode();
   int i = indexFor(hash, tables.length);
   V value = null;
   if(tables[i] != null){
      for(MyMapEntry<K, V> e = tables[i]; e != null ; e = e.next){
         if(e.hash == hash && (key.equals(e.key))){
            value = e.getValue();
         }
      }
   }
   return value;
}

一樣在找到對應的tables index時，檢查是否指到null，因此當你在使用map.get(key)時，若是

不存在的key會得到null的回傳值。但是，當確定這個key是有put進去的時候，實際上，可不

一定是tables[index]就是你要搜尋的Entry，還必須進一步的走訪檢查，hash值與key本身是否

相符。

5. remove Entry by key

這個method將會去remove掉key所組成的Entry。這個method內的code主要由本人撰寫，若有誤

請不吝指正orz

public V remove(Object key){
   int hash = key.hashCode();
   int i = indexFor(hash, tables.length);
   if(tables[i] != null){
      MyMapEntry<K, V> e = tables[i];
      MyMapEntry<K, V> prev = e;
      while(e != null){
         if(e.hash == hash && e.key.equals(key)){
            if(prev == e){
               tables[i] = e.next;
            }else{
               prev.next = e.next;
            }
            return e.value;
         }
         prev = e;
         e = e.next;
      }
   }
   return null;
}

當你指定要刪除某個key時，一樣地要去走訪，此時可不是把找到的key刪掉就沒你的事囉！

還必須將當下刪掉的Entry，將它的前一個Entry指向它的下一個Entry！

例如：

剛剛的例子我有新增兩筆Entry，剛好都在tables[2]的address內。如下：

tables[2] => key -"321"本身

key -"321"的 next => key "123"本身

key "123"的next => null

假設我要刪除key "123"，那麼我會宣告兩個變數e, prev

一開始e => tables[2] , prev => e

此時e.hash不等於要刪除key的hash，且"321" not equals "123" => 不成立

因此，prev = e，即prev繼續指向"321"本身，而e = e.next，即e指向"123"本身

再來e.hash等於要刪除key的hash，且"123" equals "123" => 成立

如此執行prev.next = e.next，表示"321"的next => "123"的next ，為null，會變成

tables[2] => key -"321"本身

key -"321"的 next => null

key "123"的next => null，這時就沒有任何一個object指向"123"（好孤單XD）

結論

1. 上面探討的概念為參考Java HashMap實作的方法，只舉put , get , remove等基本的method

2. 裡面所列舉method，有簡化部分內容，如實際的hashMap在put時還會檢查tables size是否

已超過定義的size (預設為16)，若超過HashMap還會自動擴充!!，並做資料移轉，這邊就沒

提到orz...

3. 以上的解說，純為個人的見解，若有誤請不吝指正XD

Zhi-Bin's 談天說地

搜尋此網誌

Java - How to implement basic HashMap by hashing, chaining

留言

張貼留言