0
Я изучаю хэш-таблицу с привязкой в java по ее реализации. Проблема в том, что метод get(). Значение индекса определяется с помощью key.hashCode() % table.length. Предположим, что размер таблицы равен 10, а key.hashCode() - 124, поэтому индекс найден как 4. In для каждого цикла 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;
}
}
Для хэш-таблицы _chained_ индекс никогда не увеличивается; нет никакой возможности записи, происходящей в любом другом ведре, чем 'table [4]'. –