上一章 散列（一） 主要介紹了散列的基本概念以及沖突解決方法--分離鏈表法。這一章主要介紹解決沖突的另一種方法---開放定址法。
開放定址法：嘗試另外一些單元，直到找出空的單元為止钓简。
- 線性探測法：當產生沖突時，它將尋找下一個空閑地址放入汹想。
- 平方探測法：使用 f(i) = i 2 的方法來解決沖突外邓，并且保證如果表有一半為空，并且表的大小為素數古掏，那么我們保證總能夠插入一個新的元素损话。
雙散列：使用如下探測方法：
double_hashing.png
線性探測法：
在線性探測法中，函數f是i的線性函數槽唾，典型的情形為f(i) = i 丧枪。 這相當于探測逐個單元(必要時可以回繞)以查找出一個空單元。
線性探測.png
如上圖庞萍，我們逐個插入關鍵字{89拧烦，18，49钝计，58恋博，69}。第一個沖突發(fā)生在插入49關鍵字私恬，它和89產生了沖突(因為49%10=9且89%10=9)债沮，因此，49被推入下一個空閑位置本鸣，即位置0 (注意這里是可以回繞的) ,緊接著插入58疫衩，58和18沖突了，則找下一個空閑位置永高，找到位置1.對于69的沖突也是一樣的隧土。
我們發(fā)現即使表相對較空提针，還是會發(fā)生一些占據的單元集中在一些塊區(qū)，這種現象我們成為一次聚集曹傀。
也就是說辐脖，散列在區(qū)塊中的任何關鍵字都需要多次試選單元才能解決沖突，然后將關鍵字添加進去皆愉。
實驗證明嗜价，當裝填因子(散列表中元素個數與該表大小的比)在0 ~ 0.5之間所需探測的次數時較小的，考慮到探測次數和rehash的消耗幕庐，我們一般采用0.5作為裝填因子會達到比較好的效果久锥。
線性探測.png
平方探測法
- 平方探測法是消除線性探測中一次聚集問題的解決沖突的方法。平方探測就是沖突函數為二次的探測方法异剥。
- 對于線性探測瑟由，讓散列表中填滿元素并不是一個好主意，因為此時表的性能在下降冤寿。而對于平方探測方法情況甚至更糟：一旦表被填充了一半歹苦，當表的大小不是素數時甚至在表被填充一半之前，就不能保證一次找到空的單元了督怜。這是因為最多有表的一半作為解決沖突的備選位置殴瘦。
- 定理：** 如果使用平方探測，且表的大小是素數号杠，那么當表至少有一半是空的時候蚪腋，總能夠插入一個新的元素**。
- 在探測散列表中的刪除操作姨蟋，我們不能直接執(zhí)行屉凯，因為相應的單元可能已經引起過沖突，被轉移到其他地方了眼溶。
a. 定義一個類用來標記每個位置的值以及其是否處于活動狀態(tài)(即是否存在值)
/**
* 定義一個類用來標記每個位置的情況
* @param <AnyType>
*/
private static class HashEntry<AnyType>{
//當前位置的元素值
public AnyType element;
//當前位置是否為活動狀態(tài)神得，默認為活動狀態(tài)，但若刪除后偷仿，會設置其為非活動狀態(tài)
public boolean isActive;
public HashEntry(AnyType e){
this(e, true);
}
public HashEntry(AnyType e, boolean b){
element = e;
isActive = b;
}
}
b. 定義所需變量：
//默認表的大小
private static final int DEFAULT_TABLE_SIZE = 11;
//存儲表
private HashEntry<AnyType> [] array;
//當前表的大小
private int currentSize;
c. 進行初始化操作：
//無參數構造函數
public QuadraticProbingHashTable(){
this(DEFAULT_TABLE_SIZE);
}
//有參數構造函數
public QuadraticProbingHashTable(int size){
allocateArray(size);
makeEmpty();
}
//清空表
public void makeEmpty(){
currentSize = 0;
for (int i = 0; i < array.length; i ++){
array[i] = null;
}
}
//初始化表
private void allocateArray(int size){
array = new HashEntry[nextPrime(size)];
}
c. 解決沖突位置：
/**
* 尋找空閑位置，以解決沖突
* @param x
* @return
*/
private int findPos(AnyType x){
//定義偏移量
int offset = 1;
//獲取到hash位置
int currentPos = myHash(x);
//若hash位置中存在元素,并且當前元素不等于傳入的元素
while (array[currentPos] != null && !array[currentPos].element.equals(x)){
//進行偏移
currentPos += offset;
//改變偏移量
offset += 2;
//考慮到溢出情況
if (currentPos >= array.length){
currentPos -= array.length;
}
}
return currentPos;
}
d. 插入操作：
//插入元素
public void insert(AnyType x){
//獲取到空閑位置
int currentPos = findPos(x);
//若該位置為活動狀態(tài)宵蕉，則返回酝静，表示該位置已經存在元素
//這種情況，實際上表示該位置上已經存在了該元素羡玛，那么不必重復插入
if (isActive(currentPos)){
return;
}
//否則别智，插入該元素
array[currentPos] = new HashEntry<AnyType>(x);
//判斷表的大小，超過一半稼稿，則進行rehash
if (++ currentSize > array.length / 2){
rehash();
}
}
//判斷當前位置是否為活動狀態(tài)
private boolean isActive(int currentPos){
return array[currentPos] != null && array[currentPos].isActive;
}
e. 刪除操作：
public void remove(AnyType x){
//找到位置
int currentPos = findPos(x);
//若該位置為活動狀態(tài)薄榛，則進行刪除操作
if (isActive(currentPos)){
//令該位置為非活動狀態(tài)即可
array[currentPos].isActive = false;
currentSize --;
}
}
f. 查詢操作：
public boolean contains(AnyType x){
int currentPos = findPos(x);
//返回該位置是否為活動狀態(tài)
return isActive(currentPos);
}
g. rehash操作：
private void rehash(){
HashEntry<AnyType> [] oldArray = array;
//擴充表的大小
allocateArray(nextPrime(2 * oldArray.length));
currentSize = 0;
//將舊表的數據添加到新表中
for (int i = 0; i < oldArray.length; i ++){
if (oldArray[i] != null && oldArray[i].isActive){
insert(oldArray[i].element);
}
}
}
完整代碼：
public class QuadraticProbingHashTable<AnyType> {
//無參數構造函數
public QuadraticProbingHashTable(){
this(DEFAULT_TABLE_SIZE);
}
//有參數構造函數
public QuadraticProbingHashTable(int size){
allocateArray(size);
makeEmpty();
}
//清空表
public void makeEmpty(){
currentSize = 0;
for (int i = 0; i < array.length; i ++){
array[i] = null;
}
}
public boolean contains(AnyType x){
int currentPos = findPos(x);
//返回該位置是否為活動狀態(tài)
return isActive(currentPos);
}
//插入元素
public void insert(AnyType x){
//獲取到空閑位置
int currentPos = findPos(x);
//若該位置為活動狀態(tài)讳窟，則返回，表示該位置已經存在元素
//這種情況敞恋，實際上表示該位置上已經存在了該元素丽啡，那么不必重復插入
if (isActive(currentPos)){
return;
}
//否則，插入該元素
array[currentPos] = new HashEntry<AnyType>(x);
//判斷表的大小硬猫，超過一半补箍，則進行rehash
if (++ currentSize > array.length / 2){
rehash();
}
}
public void remove(AnyType x){
//找到位置
int currentPos = findPos(x);
//若該位置為活動狀態(tài)，則進行刪除操作
if (isActive(currentPos)){
//令該位置為非活動狀態(tài)即可
array[currentPos].isActive = false;
currentSize --;
}
}
/**
* 定義一個類用來標記每個位置的情況
* @param <AnyType>
*/
private static class HashEntry<AnyType>{
//當前位置的元素值
public AnyType element;
//當前位置是否為活動狀態(tài)啸蜜，默認為活動狀態(tài)坑雅，但若刪除后，會設置其為非活動狀態(tài)
public boolean isActive;
public HashEntry(AnyType e){
this(e, true);
}
public HashEntry(AnyType e, boolean b){
element = e;
isActive = b;
}
}
//默認表的大小
private static final int DEFAULT_TABLE_SIZE = 11;
//存儲表
private HashEntry<AnyType> [] array;
//當前表的大小
private int currentSize;
//初始化表
private void allocateArray(int size){
array = new HashEntry[nextPrime(size)];
}
//判斷當前位置是否為活動狀態(tài)
private boolean isActive(int currentPos){
return array[currentPos] != null && array[currentPos].isActive;
}
/**
* 尋找空閑位置衬横，以解決沖突
* @param x
* @return
*/
private int findPos(AnyType x){
//定義偏移量
int offset = 1;
//獲取到hash位置
int currentPos = myHash(x);
//若hash位置中存在元素,并且當前元素不等于傳入的元素
while (array[currentPos] != null && !array[currentPos].element.equals(x)){
//進行偏移
currentPos += offset;
//改變偏移量
offset += 2;
//考慮到溢出情況
if (currentPos >= array.length){
currentPos -= array.length;
}
}
return currentPos;
}
private void rehash(){
HashEntry<AnyType> [] oldArray = array;
//擴充表的大小
allocateArray(nextPrime(2 * oldArray.length));
currentSize = 0;
//將舊表的數據添加到新表中
for (int i = 0; i < oldArray.length; i ++){
if (oldArray[i] != null && oldArray[i].isActive){
insert(oldArray[i].element);
}
}
}
//根據值獲取到其對應的hash位置
private int myHash(AnyType x){
int hashVal = x.hashCode();
hashVal %= array.length;
if (hashVal < 0){
hashVal += array.length;
}
return hashVal;
}
//返回下一個素數
private static int nextPrime(int n){
while (!isPrime(n)){
n ++;
}
return n;
}
//判斷是否為素數
private static boolean isPrime(int n){
for (int i = 2; i <= Math.sqrt(n); i ++){
if (n % i == 0 && n != 2){
return false;
}
}
return true;
}
}
