如果所有的鍵都是小整數(shù)己单，我們可以用一個數(shù)組來實現(xiàn)無序的符號表唉窃，將鍵作為數(shù)組的索引而數(shù)組中鍵i處存儲對應(yīng)的值。這樣我們就可以快速訪問任意鍵的值纹笼。
散列表就是這種簡易方法的擴(kuò)展纹份，并能夠處理更加復(fù)雜的類型的鍵，我們需要通過算術(shù)操作將鍵轉(zhuǎn)化為數(shù)組的索引來訪問數(shù)組中的鍵值對廷痘。
使用散列表的查找算法分為兩步蔓涧。第一步是用散列函數(shù)將被查找的鍵轉(zhuǎn)化為數(shù)組的一個索引；第二步是就是一個處理碰撞沖突的過程笋额。

• 散列函數(shù)
  Java中每種數(shù)據(jù)類型都繼承了一個能夠返回32比特整數(shù)的hashCode()方法元暴，與除留余數(shù)法結(jié)合產(chǎn)生一個0到M-1的整數(shù)：

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

• 基于拉鏈法的散列表
  散列函數(shù)能將鍵轉(zhuǎn)化為數(shù)組索引，而散列算法的第二步是處理碰撞兄猩，也就是兩個或多個散列值相同的情況茉盏。拉鏈法將大小為M的每個元素均指向一條鏈表，鏈表中的每個結(jié)點均存儲了散列值為該元素索引的鍵值對枢冤。這個方法的基本思想是選取盡可能大的M以使得所有鏈都盡可能的短鸠姨。
  public class SeparateChainingHashST<Key, Value>{
  private int N; //鍵值對總數(shù)
  private int M; //散列表大小
  private SequentialSearchST<Key, Value>[] st; //存放鏈接的對象數(shù)組
  public SeparateChainingHashST(){
  this(997);
  }
  public SeparateChainingHashST(int M){
  //創(chuàng)建M條鏈表
  this.M = M;
  st = (SequentialSearchST<Key, Value>[]) new SequentialSearchST[M];
  for (int i=0; i<M; i++)
  st[i] = new SequentialSearchST();
  }
  private int hash(Key key){
  return ( key.hashCode() & 0x7fffffff) %M;
  }
  public Value get(Key key){
  return (Value) st[hash(key)].get(key);
  public void put(Key key, Value val){
  st[hash(key)].put(key, val);
  }
  public Iterable<Key> keys()

• 基于線性探測法的散列表
  實現(xiàn)散列表的另一種方式是用大小為M的數(shù)組來存儲N個鍵值對，其中M>N淹真。依靠數(shù)組中的空位來解決碰撞沖突讶迁。基于這種策略的所有方法被稱為開放地址散列表核蘸。
  開放地址散列表實現(xiàn)的最簡單方法是線性探測法——當(dāng)碰撞發(fā)生時巍糯，我們直接檢測下一個位置，于是產(chǎn)生三種結(jié)果：

  • 命中值纱，該位置的鍵和被查找的鍵相同鳞贷；
  • 未命中，鍵為空虐唠；
  • 繼續(xù)查找搀愧，該位置的鍵與被查找的鍵不同。

  開放地址類的散列表的核心思想是與其將內(nèi)存用作鏈表疆偿，不如將它們作為散列表的空元素咱筛。

  public class LinearProbingHashST<Key, Value>{
      private int N;
      private int M;
      private Key[] keys;
      private Value[] vals;
      public LinearProbingHashST(){
          keys = (Key[]) new Object[M];
          vals = (Value[]) new Object[M];
      }
      private int hash(Key key){
          return (key.hashCode() & 0x7fffffff ) %M;
      }
      private resize();
      public void put(Key key, Value val){
          if( N >= M/2) resize(2*M);
          int i;
          for( i =hash(key); keys[i] ! = null; i = (i+1)%M){
              if( keys[i].equals(key)){
                  vals[i] = val;
                  return;
              }
              keys[i] = key;
              vals[i] = val;
              N++;
      }
  
      public Value get(Key key){
          for( int i = hash(key); keys[i] != null; i = (i+1)%M)
              if(keys[i].equals(key))
                  return vals[i];
          return null;
      }
  }
  

對于線性探測法的刪除操作，直接將該鍵的位置設(shè)置為null是不行的杆故，因為這樣將會導(dǎo)致該鍵位置之后的元素都無法被找到迅箩。
public void delete(Key key){
if( !contains(key)) return;
int i = hash(key);
while(!key.equals(keys[i]))
i = (i+1) % M;
keys[i] = null;
vals[i] = null;
i = (i+1) % M;
while( keys[i] != null){
Key keyToRedo = keys[i];
Value valToRedo = vals[i];
keys[i] = null;
vals[i] = null;
N--;
put(keyToRedo, valToRedo);
i = (i+1) % M;
}
N--;
if( N>0 && N <= M/8) resize(M/2);
}