散列表的原理與Java實現(xiàn)方法詳解

本文實例講述了散列表的原理與Java實現(xiàn)方法。分享給大家供大家參考，具體如下：

概述

符號表是一種用于存儲鍵值對（key-value pair）的數(shù)據(jù)結(jié)構(gòu)，我們平常經(jīng)常使用的數(shù)組也可以看做是一個特殊的符號表，數(shù)組中的“鍵”即為數(shù)組索引，值為相應(yīng)的數(shù)組元素。也就是說，當(dāng)符號表中所有的鍵都是較小的整數(shù)時，我們可以使用數(shù)組來實現(xiàn)符號表，將數(shù)組的索引作為鍵，而索引處的數(shù)組元素即為鍵對應(yīng)的值，但是這一表示僅限于所有的鍵都是比較小的整數(shù)時，否則可能會使用一個非常大的數(shù)組。散列表是對以上策略的一種“升級”，但是它可以支持任意的鍵而并沒有對它們做過多的限定。對于基于散列表實現(xiàn)的符號表，若我們要在其中查找一個鍵，需要進(jìn)行以下步驟：

• 首先我們使用散列函數(shù)將給定鍵轉(zhuǎn)化為一個“數(shù)組的索引”，理想情況下，不同的key會被轉(zhuǎn)為不同的索引，但在實際應(yīng)用中我們會遇到不同的鍵轉(zhuǎn)為相同的索引的情況，這種情況叫做碰撞。解決碰撞的方法我們后面會具體介紹。
• 得到了索引后，我們就可以像訪問數(shù)組一樣，通過這個索引訪問到相應(yīng)的鍵值對。

以上就是散列表的核心思想，散列表是時空權(quán)衡的經(jīng)典例子。當(dāng)我們的空間無限大時，我們可以直接使用一個很大的數(shù)組來保存鍵值對，并用key作為數(shù)組索引，因為空間不受限，所以我們的鍵的取值可以無窮大，因此查找任何鍵都只需進(jìn)行一次普通的數(shù)組訪問。反過來，若對查找操作沒有任何時間限制，我們就可以直接使用鏈表來保存所有鍵值對，這樣把空間的使用降到了最低，但查找時只能順序查找。在實際的應(yīng)用中，我們的時間和空間都是有限的，所以我們必須在兩者之間做出權(quán)衡，散列表就在時間和空間的使用上找到了一個很好的平衡點(diǎn)。散列表的一個優(yōu)勢在于我們只需調(diào)整散列算法的相應(yīng)參數(shù)而無需對其他部分的代碼做任何修改就能夠在時間和空間的權(quán)衡上做出策略調(diào)整。

散列函數(shù)

介紹散列函數(shù)前，我們先來介紹幾個散列表的基本概念。在散列表內(nèi)部，我們使用桶（bucket）來保存鍵值對，我們前面所說的數(shù)組索引即為桶號，決定了給定的鍵存于散列表的哪個桶中。散列表所擁有的桶數(shù)被稱為散列表的**容量（capacity）。

現(xiàn)在假設(shè)我們的散列表中有M個桶，桶號為0到M-1。我們的散列函數(shù)的功能就是把任意給定的key轉(zhuǎn)為[0, M-1]上的整數(shù)。我們對散列函數(shù)有兩個基本要求：一是計算時間要短，二是盡可能把鍵分布在不同的桶中。對于不同類型的鍵，我們需要使用不同的散列函數(shù)，這樣才能保證有比較好的散列效果。

我們使用的散列函數(shù)應(yīng)該盡可能滿足均勻散列假設(shè)，以下對均勻散列假設(shè)的定義來自于Sedgewick的《算法》一書：

（均勻散列假設(shè)）我們使用的散列函數(shù)能夠均勻并獨(dú)立地將所有的鍵散布于0到M – 1之間。

以上定義中有兩個關(guān)鍵字，第一個是均勻，意思是我們對每個鍵計算而得的桶號有M個“候選值”，而均勻性要求這M個值被選中的概率是均等的；第二個關(guān)鍵字是獨(dú)立，它的意思是，每個桶號被選中與否是相互獨(dú)立的，與其他桶號是否被選中無關(guān)。這樣一來，滿足均勻性與獨(dú)立性能夠保證鍵值對在散列表的分布盡可能的均勻，不會出現(xiàn)“許多鍵值對被散列到同一個桶，而同時許多桶為空”的情況。

顯然，設(shè)計一個較好的滿足均勻散列假設(shè)的散列函數(shù)是不容易的，好消息是通常我們無需設(shè)計它，因為我們可以直接使用一些基于概率統(tǒng)計的高效的實現(xiàn)，比如Java中許多常用的類都重寫了hashCode方法（Object類的hashCode方法默認(rèn)返回對象的內(nèi)存地址），用于為該類型對象返回一個hashCode，通常我們用這個hashCode除以桶數(shù)M的余數(shù)就可以獲取一個桶號。下面我們以Java中的一些類為例，來介紹一下針對不同數(shù)據(jù)類型的散列函數(shù)的實現(xiàn)。

String類的hashCode方法

String類的hashCode方法如下所示：

public int hashCode() {
 int h = hash;
 if (h == 0 && value.length > 0) {
  char val[] = value;
  for (int i = 0; i < value.length; i++) {
   h = 31 * h + val[i];
  }
  hash = h;
 }
 return h;
}

hashCode方法中的value是一個char[]數(shù)組，存儲中字符串的的每字符。我們可以看到在方法的最開始我們會把hash賦給h，這個hash就表示之前計算的hashCode，這樣以來若之前已經(jīng)計算過這個字符串對象的hashCode，這次我們就無需再計算了，直接返回之前計算過得即可。這種把hashCode緩存的策略只對不可變對象有效，因為不可變對象的hashCode是不會變的。

根據(jù)上面的代碼我們可以知道，若h為null，意味著我們是第一次計算hashCode，if語句體中就是hashCode的具體計算方法。假設(shè)我們的字符串對象str包含4個字符，ck表示的是字符串中的第k個字符（從0開始計數(shù)），那么str的hashCode就等于：31 * (31 * (31 * c0 + c1) + c2) +c3。

數(shù)值類型的hashCode方法

這里我們以Integer和Double為例，介紹一下數(shù)值類型的hashCode方法的一般實現(xiàn)。
Integer類的hashCode方法如下：

public int hashCode() {
 return Integer.hashCode(value);
}
public static int hashCode(int value) {
 return value;
}

其中value表示Integer對象所包裝的整型值，所以Integer類的hashCode方法僅僅是簡單的返回了自身的值。

我們再來看一下Double類的hashCode方法：

@Override
public int hashCode() {
 return Double.hashCode(value);
}
public static int hashCode(double value) {
 long bits = doubleToLongBits(value);
 return (int)(bits ^ (bits >>> 32));
}

我們可以看到Double類的hashCode方法首先會將它的值轉(zhuǎn)為long類型，然后返回低32位和高32位的異或的結(jié)果作為hashCode。

Date類的hashCode方法

前面我們介紹的數(shù)據(jù)類型都可以看做一種數(shù)值型（String可以看做一個整型數(shù)組），那么對于非數(shù)值類型對象的hashCode要怎么計算呢，這里我們以Date類為例簡單的介紹一下。Date類的hashCode方法如下：

public int hashCode() {
 long ht = this.getTime();
 return (int) ht ^ (int) (ht >> 32);
}

我們可以看到，它的hashCode方法的實現(xiàn)非常簡單，只是返回了Date對象所封裝的時間的低32位和高32位的異或結(jié)果。從Date類的hashCode的實現(xiàn)我們可以了解到，對于非數(shù)值類型的hashCode的計算，我們需要選取一些能區(qū)分各個類實例的實例域來作為計算的因子。比如對于Date類來說，通常具有相同的時間的Date對象我們認(rèn)為它們相等，因此也就具有相同的hashCode。這里我們需要說明一下，對于等價的兩個對象（也就是調(diào)用equals方法返回true），它們的hashCode必須相同，而反之則不然。

由hashCode獲取桶號

前面我們介紹了計算對象hashCode的一些方法，那么我們獲取了hashCode之后，如何進(jìn)一步得到桶號呢？一個直接的辦法就是直接拿得到的hashCode除以capacity（桶的數(shù)量），然后用所得的余數(shù)作為桶號。不過在Java中，hashCode是int型的，而Java中的int型均為有符號，所以我們要是直接使用返回的hashCode的話可能會得到一個負(fù)數(shù)，顯然桶號是不能為負(fù)的。所以我們先將返回的hashCode轉(zhuǎn)變?yōu)橐粋€非負(fù)整數(shù)，再用它除以capacity取余數(shù)，作為key的對應(yīng)桶號，具體代碼如下：

private int hash(K key) { return (x.hashCode() & 0x7fffffff) % M;}

現(xiàn)在我們已經(jīng)知道了如何通過一個鍵獲取桶號，那么接下來我們來介紹使用散列表查找的第二步——處理碰撞。

使用拉鏈法處理碰撞

使用不同的碰撞處理方式，我們便得到了散列表的不同實現(xiàn)。首先我們要介紹的是使用拉鏈法來處理碰撞的散列表的實現(xiàn)。以這種方式實現(xiàn)的散列表，每個桶里都存放了一個鏈表。初始時所有鏈表均為空，當(dāng)一個鍵被散列到一個桶時，這個鍵就成為相應(yīng)桶中鏈表的首結(jié)點(diǎn)，之后若再有一個鍵被散列到這個桶（即發(fā)生碰撞），第二個鍵就會成為鏈表的第二個結(jié)點(diǎn)，以此類推。這樣一來，當(dāng)桶數(shù)為M，散列表中存儲的鍵值對數(shù)目為N時，平均每個桶中的鏈表包含的結(jié)點(diǎn)數(shù)為N / M。因此，當(dāng)我們查找一個鍵時，首先通過散列函數(shù)確定它所在的桶，這一步所需時間為O(1)；然后我們依次比較桶中結(jié)點(diǎn)的鍵與給定鍵，若相等則找到了指定鍵值對，這一步所需時間為O(N / M)。所以查找操作所需的時間為O(N / M)，而通常我們都能夠保證N是M的常數(shù)倍，所以散列表的查找操作的時間復(fù)雜度為O(1)，同理我們也可以得到插入操作的復(fù)雜度也為O(1)。

理解了以上的描述，實現(xiàn)基于拉鏈法的散列表也就很容易了，這里簡單起見，我們直接使用前面的SeqSearchList作為桶中的鏈表，參考代碼如下：

public class ChainingHashMap<K, V> {
 private int num; //當(dāng)前散列表中的鍵值對總數(shù)
 private int capacity; //桶數(shù)
 private SeqSearchST<K, V>[] st; //鏈表對象數(shù)組
 public ChainingHashMap(int initialCapacity) {
  capacity = initialCapacity;
  st = (SeqSearchST<K, V>[]) new Object[capacity];
  for (int i = 0; i < capacity; i++) {
   st[i] = new SeqSearchST<>();
  }
 }
 private int hash(K key) {
  return (key.hashCode() & 0x7fffffff) % capacity;
 }
 public V get(K key) {
   return st[hash(key)].get(key);
 }
 public void put(K key, V value) {
  st[hash(key)].put(key, value);
 }
}

在上面的實現(xiàn)中，我們固定了散列表的桶數(shù)，當(dāng)我們明確知道我們要插入的鍵值對數(shù)目最多只能到達(dá)桶數(shù)的常數(shù)倍時，固定桶數(shù)是完全可行的。但是若鍵值對數(shù)目會增長到遠(yuǎn)遠(yuǎn)大于桶數(shù)，我們就需要動態(tài)調(diào)整桶數(shù)的能力。實際上，散列表中的鍵值對數(shù)與桶數(shù)的比值叫做負(fù)載因子（load factor）。通常負(fù)載因子越小，我們進(jìn)行查找所需時間就越短，而空間的使用就越大；若負(fù)載因子較大，則查找時間會變長，但是空間使用會減小。比如，Java標(biāo)準(zhǔn)庫中的HashMap就是基于拉鏈法實現(xiàn)的散列表，它的默認(rèn)負(fù)載因子為0.75。HashMap實現(xiàn)動態(tài)調(diào)整桶數(shù)的方式是基于公式loadFactor = maxSize / capacity，其中maxSize為支持存儲的最大鍵值對數(shù)，而loadFactor和capacity（桶數(shù)）都會在初始化時由用戶指定或是由系統(tǒng)賦予默認(rèn)值。當(dāng)HashMap中的鍵值對的數(shù)目達(dá)到了maxSize時，就會增大散列表中的桶數(shù)。

以上代碼中還用到了SeqSearchST，實際上這就是一個基于鏈表的符號表實現(xiàn)，支持向其中添加key-value pair，查找指定鍵時使用的是順序查找，它的代碼如下：

public class SeqSearchST<K, V> {
 private Node first;
 private class Node {
  K key;
  V val;
  Node next;
  public Node(K key, V val, Node next) {
   this.key = key;
   this.val = val;
   this.next = next;
  }
 }
 public V get(K key) {
  for (Node node = first; node != null; node = node.next) {
   if (key.equals(node.key)) {
    return node.val;
   }
  }
  return null;
 }
 public void put(K key, V val) {
  //先查找表中是否已存在相應(yīng)key
  Node node;
  for (node = first; node != null; node = node.next) {
   if (key.equals(node.key)) {
    node.val = val;
    return;
   }
  }
  //表中不存在相應(yīng)key
  first = new Node(key, val, first);
 }
}

使用線性探測法處理碰撞

基本原理與實現(xiàn)

線性探測法是另一種散列表的實現(xiàn)策略的具體方法，這種策略叫做開放定址法。開放定址法的主要思想是：用大小為M的數(shù)組保存N個鍵值對，其中M > N，數(shù)組中的空位用于解決碰撞問題。

線性探測法的主要思想是：當(dāng)發(fā)生碰撞時（一個鍵被散列到一個已經(jīng)有鍵值對的數(shù)組位置），我們會檢查數(shù)組的下一個位置，這個過程被稱作線性探測。線性探測可能會產(chǎn)生三種結(jié)果：

• 命中：該位置的鍵與要查找的鍵相同；
• 未命中：該位置為空；
• 該位置的鍵和被查找的鍵不同。

當(dāng)我們查找某個鍵時，首先通過散列函數(shù)得到一個數(shù)組索引后，之后我們就開始檢查相應(yīng)位置的鍵是否與給定鍵相同，若不同則繼續(xù)查找（若到數(shù)組末尾也沒找到就折回數(shù)組開頭），直到找到該鍵或遇到一個空位置。由線性探測的過程我們可以知道，若數(shù)組已滿的時候我們再向其中插入新鍵，會陷入無限循環(huán)之中。

理解了以上原理，要實現(xiàn)基于線性探測法的散列表也就不難了。這里我們使用數(shù)組keys保存散列表中的鍵，數(shù)組values保存散列表中的值，兩個數(shù)組同一位置上的元素共同確定一個散列表中的鍵值對。具體代碼如下：

public class LinearProbingHashMap<K, V> {
 private int num; //散列表中的鍵值對數(shù)目
 private int capacity;
 private K[] keys;
 private V[] values;
 public LinearProbingHashMap(int capacity) {
  keys = (K[]) new Object[capacity];
  values = (V[]) new Object[capacity];
  this.capacity = capacity;
 }
 private int hash(K key) {
  return (key.hashCode() & 0x7fffffff) % capacity;
 }
 public V get(K key) {
  int index = hash(key);
  while (keys[index] != null && !key.equals(keys[index])) {
   index = (index + 1) % capacity;
  }
  return values[index]; //若給定key在散列表中存在會返回相應(yīng)value，否則這里返回的是null
 }
 public void put(K key, V value) {
  int index = hash(key);
  while (keys[index] != null && !key.equals(keys[index])) {
   index = (index + 1) % capacity;
  }
  if (keys[index] == null) {
   keys[index] = key;
   values[index] = value; return;
  }
  values[index] = value; num++;
 }
}

動態(tài)調(diào)整數(shù)組大小

在我們上面的實現(xiàn)中，數(shù)組的大小為桶數(shù)的2倍，不支持動態(tài)調(diào)整數(shù)組大小。而在實際應(yīng)用中，當(dāng)負(fù)載因子（鍵值對數(shù)與數(shù)組大小的比值）接近1時，查找操作的時間復(fù)雜度會接近O(n)，而當(dāng)負(fù)載因子為1時，根據(jù)我們上面的實現(xiàn)，while循環(huán)會變?yōu)橐粋€無限循環(huán)。顯然我們不想讓查找操作的復(fù)雜度退化至O(n)，更不想陷入無限循環(huán)。所以有必要實現(xiàn)動態(tài)增長數(shù)組來保持查找操作的常數(shù)時間復(fù)雜度。當(dāng)鍵值對總數(shù)很小時，若空間比較緊張，可以動態(tài)縮小數(shù)組，這取決于實際情況。

要實現(xiàn)動態(tài)改變數(shù)組大小，只需要在上面的put方法最開始加上一個如下的判斷：

if (num == capacity / 2) {
 resize(2 * capacity);
}

resize方法的邏輯也很簡單：

private void resize(int newCapacity) {
 LinearProbingHashMap<K, V> hashmap = new LinearProbingHashMap<>(newCapacity);
 for (int i = 0; i < capacity; i++) {
  if (keys[i] != null) {
   hashmap.put(keys[i], values[i]);
  }
 }
 keys = hashmap.keys;
 values = hashmap.values;
 capacity = hashmap.capacity;
}

關(guān)于負(fù)載因子與查找操作的性能的關(guān)系，這里貼出《算法》（Sedgewick等）中的一個結(jié)論：

在一張大小為M并含有N = a*M（a為負(fù)載因子）個鍵的基于線性探測的散列表中，若散列函數(shù)滿足均勻散列假設(shè)，命中和未命中的查找所需的探測次數(shù)分別為：~ 1/2 * (1 + 1/(1-a))和~1/2*(1 + 1/(1-a)^2)

關(guān)于以上結(jié)論，我們只需要知道當(dāng)a約為1/2時，查找命中和未命中所需的探測次數(shù)分別為1.5次和2.5次。還有一點(diǎn)就是當(dāng)a趨近于1時，以上結(jié)論中的估計值的精度會下降，不過我們在實際應(yīng)用中不會讓負(fù)載因子接近1，為了保持良好的性能，在上面的實現(xiàn)中我們應(yīng)保持a不超過1/2。

參考資料

《算法（第四版）》（Sedgewick等）

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對大家java程序設(shè)計有所幫助。