我正在研究通过哈希表在Java中实现的哈希表。问题在于get()
方法。索引值由确定key.hashCode() % table.length
。假设表的大小为10
和key.hashCode()为124
,则找到的索引为4
。在从每个循环table[index]
开始时table[4]
,AFAIK索引正在逐一递增4,5,6,7... so on
。但是指数0,1,2,3
呢?他们被检查了吗?(我认为不是)是否有可能在其中一个索引上出现密钥?(我想是的)。另一个问题是有null
检查,但最初没有null
为key
和分配任何任务value
。那么如何进行检查呢?被null
指定为尽快private LinkedList<Entry<K, V>>[] table
宣布?
// Data Structures: Abstraction and Design Using Java, Koffman, Wolfgang
package KW.CH07;
import java.util.AbstractMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.StringJoiner;
/**
* Hash table implementation using chaining.
* @param <K> The key type
* @param <V> The value type
* @author Koffman and Wolfgang
**/
public class HashtableChain<K, V>
// Insert solution to programming project 7, chapter -1 here
implements KWHashMap<K, V> {
/** The table */
private LinkedList<Entry<K, V>>[] table;
/** The number of keys */
private int numKeys;
/** The capacity */
private static final int CAPACITY = 101;
/** The maximum load factor */
private static final double LOAD_THRESHOLD = 3.0;
// Note this is equivalent to java.util.AbstractMap.SimpleEntry
/** Contains key-value pairs for a hash table.
@param <K> the key type
@param <V> the value type
*/
public static class Entry<K, V>
// Insert solution to programming project 6, chapter -1 here
{
/** The key */
private final K key;
/** The value */
private V value;
/**
* Creates a new key-value pair.
* @param key The key
* @param value The value
*/
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
/**
* Retrieves the key.
* @return The key
*/
@Override
public K getKey() {
return key;
}
/**
* Retrieves the value.
* @return The value
*/
@Override
public V getValue() {
return value;
}
/**
* Sets the value.
* @param val The new value
* @return The old value
*/
@Override
public V setValue(V val) {
V oldVal = value;
value = val;
return oldVal;
}
// Insert solution to programming exercise 3, section 4, chapter 7 here
}
// Constructor
public HashtableChain() {
table = new LinkedList[CAPACITY];
}
// Constructor for test purposes
HashtableChain(int capacity) {
table = new LinkedList[capacity];
}
/**
* Method get for class HashtableChain.
* @param key The key being sought
* @return The value associated with this key if found;
* otherwise, null
*/
@Override
public V get(Object key) {
int index = key.hashCode() % table.length;
if (index < 0) {
index += table.length;
}
if (table[index] == null) {
return null; // key is not in the table.
}
// Search the list at table[index] to find the key.
for (Entry<K, V> nextItem : table[index]) {
if (nextItem.getKey().equals(key)) {
return nextItem.getValue();
}
}
// assert: key is not in the table.
return null;
}
/**
* Method put for class HashtableChain.
* @post This key-value pair is inserted in the
* table and numKeys is incremented. If the key is already
* in the table, its value is changed to the argument
* value and numKeys is not changed.
* @param key The key of item being inserted
* @param value The value for this key
* @return The old value associated with this key if
* found; otherwise, null
*/
@Override
public V put(K key, V value) {
int index = key.hashCode() % table.length;
if (index < 0) {
index += table.length;
}
if (table[index] == null) {
// Create a new linked list at table[index].
table[index] = new LinkedList<>();
}
// Search the list at table[index] to find the key.
for (Entry<K, V> nextItem : table[index]) {
// If the search is successful, replace the old value.
if (nextItem.getKey().equals(key)) {
// Replace value for this key.
V oldVal = nextItem.getValue();
nextItem.setValue(value);
return oldVal;
}
}
// assert: key is not in the table, add new item.
table[index].addFirst(new Entry<>(key, value));
numKeys++;
if (numKeys > (LOAD_THRESHOLD * table.length)) {
rehash();
}
return null;
}
/** Returns true if empty
@return true if empty
*/
@Override
public boolean isEmpty() {
return numKeys == 0;
}
}
假设表的大小为10,key.hashCode()为124,因此找到的索引为4。在每个循环中,table [index]从table [4]开始
正确的。
没有空检查,但最初没有为键和值分配任何空值。那么如何进行检查呢?
初始化对象数组时,所有值都设置为null
。
索引正递增1,4,5,6,7 ...依此类推。但是索引0、1、2、3呢?他们被检查了吗?(我认为不是)是否有可能在其中一个索引上出现密钥?(我想是的)。
看起来这里有些误会。首先,考虑一下这样的数据结构(已经添加了数据):
table:
[0] -> null
[1] -> LinkedList -> item 1 -> item 2 -> item 3
[2] -> LinkedList -> item 1
[3] -> null
[4] -> LinkedList -> item 1 -> item 2
[5] -> LinkedList -> item 1 -> item 2 -> item 3 -> item 4
[6] -> null
另一个重要的一点是,给定的哈希码key
不应更改,因此它将始终映射到表中的同一索引。
因此,假设我们get
用哈希码将其映射为3的值进行调用,那么我们知道该值不在表中:
if (table[index] == null) {
return null; // key is not in the table.
}
如果另一个键映射为1,那么我们需要遍历LinkedList:
// LinkedList<Entry<K, V>> list = table[index]
for (Entry<K, V> nextItem : table[index]) {
// iterate over item 1, item 2, item 3 until we find one that is equal.
if (nextItem.getKey().equals(key)) {
return nextItem.getValue();
}
}
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句