上一章 散列(一) 主要介紹了散列的基本概念以及沖突解決方法--分離鏈表法。這一章主要介紹解決沖突的另一種方法---開放定址法。
開放定址法:嘗試另外一些單元,直到找出空的單元為止钓简。
- 線性探測法:當產生沖突時,它將尋找下一個空閑地址放入汹想。
- 平方探測法:使用 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;
}
}