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

概述

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

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

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

散列函數(shù)

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

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

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

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

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

顯然，設(shè)計(jì)一個(gè)較好的滿足均勻散列假設(shè)的散列函數(shù)是不容易的，好消息是通常我們無需設(shè)計(jì)它，因?yàn)槲覀兛梢灾苯邮褂靡恍┗诟怕式y(tǒng)計(jì)的高效的實(shí)現(xiàn)，比如Java中許多常用的類都重寫了hashCode方法（Object類的hashCode方法默認(rèn)返回對(duì)象的內(nèi)存地址），用于為該類型對(duì)象返回一個(gè)hashCode，通常我們用這個(gè)hashCode除以桶數(shù)M的余數(shù)就可以獲取一個(gè)桶號(hào)。下面我們以Java中的一些類為例，來介紹一下針對(duì)不同數(shù)據(jù)類型的散列函數(shù)的實(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是一個(gè)char[]數(shù)組，存儲(chǔ)中字符串的的每字符。我們可以看到在方法的最開始我們會(huì)把hash賦給h，這個(gè)hash就表示之前計(jì)算的hashCode，這樣以來若之前已經(jīng)計(jì)算過這個(gè)字符串對(duì)象的hashCode，這次我們就無需再計(jì)算了，直接返回之前計(jì)算過得即可。這種把hashCode緩存的策略只對(duì)不可變對(duì)象有效，因?yàn)椴豢勺儗?duì)象的hashCode是不會(huì)變的。

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

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

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

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

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

我們?cè)賮砜匆幌翫ouble類的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方法首先會(huì)將它的值轉(zhuǎn)為long類型，然后返回低32位和高32位的異或的結(jié)果作為hashCode。

Date類的hashCode方法

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

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

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

由hashCode獲取桶號(hào)

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

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

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

使用拉鏈法處理碰撞

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

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

public class ChainingHashMap<K, V> {
 private int num; //當(dāng)前散列表中的鍵值對(duì)總數(shù)
 private int capacity; //桶數(shù)
 private SeqSearchST<K, V>[] st; //鏈表對(duì)象數(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);
 }
}

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

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

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);
 }
}

使用線性探測法處理碰撞

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

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

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

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

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

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

public class LinearProbingHashMap<K, V> {
 private int num; //散列表中的鍵值對(duì)數(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在散列表中存在會(huì)返回相應(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++;
 }
}

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

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

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

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等）中的一個(gè)結(jié)論：

在一張大小為M并含有N = a*M（a為負(fù)載因子）個(gè)鍵的基于線性探測的散列表中，若散列函數(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í)，查找命中和未命中所需的探測次數(shù)分別為1.5次和2.5次。還有一點(diǎn)就是當(dāng)a趨近于1時(shí)，以上結(jié)論中的估計(jì)值的精度會(huì)下降，不過我們?cè)趯?shí)際應(yīng)用中不會(huì)讓負(fù)載因子接近1，為了保持良好的性能，在上面的實(shí)現(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緩存操作技巧匯總》

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

最新評(píng)論