0
帖子详细
在数据结构课程的通用地图，我获得了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;
}
}