title: HashMap

date: 2015-09-06 19:45:38

tags: [java,algorithm]

categories: java

Java最基本的資料結構有數組和連結清單。

數組的特點是空間連續（大小固定）、尋址迅速，但是插入和删除時需要移動元素，是以查詢快，增加删除慢。

連結清單恰好相反，可動态增加或減少空間以适應新增和删除元素，但查找時隻能順着一個個節點查找，是以增加删除快，查找慢。

那麼問題來了，有沒有一種綜合數組和連結清單優點的資料結構呢？

The answer is HashMap!

HashMap

首先看看HashMap是怎麼個存儲方式，下圖無明确作者，在此不添加Reference了！ 尊重原創！

如圖，hash表就是由資料+連結清單組成的。首先數組每個元素存儲一個連結清單節點，通過一定算法，比如

hash(key)%length

來存儲後續的節點，比如31%16=15，就放到元素15開頭的連結清單中。

看了HashMap的源碼，其實HashMap是基于一個線性的數組結構來實作的：

o n e： HashMap内部定義了一個Entry<k,v>數組

t w o：

static class Entry<k,v> implements Map<k,v>

,并且具有key/value/next等屬性,類似JavaBean

three： 也就是，Entry[]資料存儲了Map<k,v>這種結構的資料

分析一段源碼，來自HashMap中的put()方法：

public V put(K key, V value) {
          if (key == null)
              return putForNullKey(value);
          int hash = hash(key.hashCode());
          int i = indexFor(hash, table.length);
          for (Entry<K,V> e = table[i]; e != null; e = e.next) {
              Object k;
              if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                  V oldValue = e.value;
                  e.value = value;
                  e.recordAccess(this);
                  return oldValue;
             }
          } 
        modCount++; 
        addEntry(hash, key, value, i);
        return null;
    }	
           

其實思路并不複雜，通過一個hash算法得到hash值，通過hash值得到Entry數組下标index，然後找到數組位置，通過鍊式結構比對Key值，get it！

那麼，問題在這，這是源碼裡的hash算法：

static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); }

我真是驚呆了，費腦筋~

雖然能猜出來其作用，大體大概是防止hash沖突，但是具體為什麼這樣，而不是那樣，我解釋不清楚了=。=！

計算index的方法，倒是很清新，用到了效率最高的位運算，其中length-1防止數組越界：

static int indexFor(int h, int length) { return h & (length-1); }

另，解決hash沖突的方法：

1. 開放定址法（線性探測再散列，二次探測再散列，僞随機探測再散列）
2. 再哈希法
3. 鍊位址法
4. 建立一個公共溢出區

顯然HashMap采用的是鍊位址法

EOF

I am a slow walker, but I never walk backwards.