帖子詳細
在數據結構課程的通用地圖,我獲得了Java源代碼的「二次探測哈希表」級,並要求實現一個通用的地圖(與得到和把方法)並將密鑰/定義對存儲在散列表中。我在閱讀本書時理解這些內容,但發現很難用編程語言(Java)來實現。我認爲問題的一部分是確切地理解問題的要求,部分是Java編程體驗的不足之處。我希望能得到一些關於如何處理這類問題的建議,並填寫我錯過的任何Java知識。實現使用哈希表中的Java
一些問題我已經
什麼是哈希表類相對於一般的地圖我應該創建函數?哈希表有幾種方法,包括得到,插入,刪除,翻版等...是哈希表來生成一個散列值作爲地圖類要使用的密鑰的目的是什麼?密鑰和定義存儲在散列表中還是將它們存儲在地圖中?如果哈希表已經完成了所有這些,那麼製作一張地圖有什麼意義呢?
有人可以幫我理解如何解決這樣的問題嗎?什麼是一些可能對我有幫助的參考,或者是專門針對這個問題,或者是對如何有效和有條理地完成這種練習的理解?
我很感激我能得到的任何幫助。我包括書中的代碼以幫助說明問題。
二次探查哈希表碼課本
public class QuadraticProbingHashTable<AnyType> {
public QuadraticProbingHashTable() {
this(DEFAULT_TABLE_SIZE);
}
public QuadraticProbingHashTable(int size) {
allocateArray(size);
doClear();
}
public boolean insert(AnyType x) {
int currentPos = findPos(x);
if(isActive(currentPos)) return false;
array[currentPos] = new HashEntry<>(x, true);
theSize++;
if(++occupied > array.length/2) rehash();
return true;
}
private void rehash() {
HashEntry<AnyType>[] oldArray = array;
allocateArray(2 * oldArray.length);
occupied = 0;
theSize = 0;
for(HashEntry<AnyType> entry : oldArray)
if(entry != null && entry.isActive) insert(entry.element);
}
private int findPos(AnyType x) {
int offset = 1;
int currentPos = myhash(x);
while(array[currentPos] != null && !array[currentPos].element.equals(x)) {
currentPos += offset;
offset += 2;
if(currentPos >= array.length) currentPos -= array.length;
}
return currentPos;
}
public boolean remove(AnyType x) {
int currentPos = findPos(x);
if(isActive(currentPos)) {
array[currentPos].isActive = false;
theSize--;
return true;
} else return false;
}
public int size() {
return theSize;
}
public int capacity() {
return array.length;
}
public boolean contains(AnyType x) {
int currentPos = findPos(x);
return isActive(currentPos);
}
public AnyType get(AnyType x) {
int currentPos = findPos(x);
if(isActive(currentPos)) return array[currentPos].element;
else return null;
}
private boolean isActive(int currentPos) {
return array[currentPos] != null && array[currentPos].isActive;
}
public void makeEmpty() {
doClear();
}
private void doClear() {
occupied = 0;
for(int i = 0; i < array.length; i++) array[i] = null;
}
private int myhash(AnyType x) {
int hashVal = x.hashCode();
hashVal %= array.length;
if(hashVal < 0) hashVal += array.length;
return hashVal;
}
private static class HashEntry<AnyType> {
public AnyType element;
public boolean isActive;
public HashEntry(AnyType e) {
this(e, true);
}
public HashEntry(AnyType e, boolean i) {
element = e;
isActive = i;
}
}
private static final int DEFAULT_TABLE_SIZE = 101;
private HashEntry<AnyType>[] array;
private int occupied;
private int theSize;
private void allocateArray(int arraySize) {
array = new HashEntry[nextPrime(arraySize)];
}
private static int nextPrime(int n) {
if(n % 2 == 0) n++;
for(; !isPrime(n); n += 2) ;
return n;
}
private static boolean isPrime(int n) {
if(n == 2 || n == 3) return true;
if(n == 1 || n % 2 == 0) return false;
for(int i = 3; i * i <= n; i += 2)
if(n % i == 0) return false;
return true;
}
}
地圖骨架課本
class Map<KeyType,ValueType> {
public Map()
public void put(KeyType key, ValueType val)
public ValueType get(KeyType key)
public boolean isEmpty()
public void makeEmpty()
private QuadraticProbingHashTable<Entry<KeyType,ValueType>> items;
private static class Entry<KeyType,ValueType> {
KeyType key;
ValueType value;
}
}