Мобильная версияЕсли добавление в таблицу приведет к превышению коэффициента нагрузки (LF) (т. е. больше, не больше или равно) константу максимального коэффициента загрузки, указанную в файле Java, размер таблицы следует изменить, чтобы она имела емкость 2n + 1.
Я пытаюсь изменить его размер до 2n+1, где n — исходный размер массива. Но почему-то это не работает? Всякий раз, когда я тестирую это, размер массива никогда не изменяется так, как я хочу.
Я считаю, что проблема может заключаться в одном из этих фрагментов кода:
- Размещение вызываемого метода внутри метода put:
Код: Выделить всё
if ((countEntries(table)) / table.length > MAX_LOAD_FACTOR) { resizeBackingTable(table.length); } - Или код внутри самого метода resizeBackingTable.
Код: Выделить всё
private void resizeBackingTable(int length) { // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)! ExternalChainingMapEntry[] newBackingArray = (ExternalChainingMapEntry[]) new ExternalChainingMapEntry[2 * length + 1]; for (ExternalChainingMapEntry entry : table) { while (entry != null) { int hash = calculateHash(entry.getKey(), newBackingArray.length); ExternalChainingMapEntry next = entry.getNext(); entry.setNext(newBackingArray[hash]); newBackingArray[hash] = entry; entry = next; } } table = newBackingArray; }
Код: Выделить всё
import java.util.NoSuchElementException;
/**
* Your implementation of a ExternalChainingHashMap.
*/
public class ExternalChainingHashMap {
/*
* The initial capacity of the ExternalChainingHashMap when created with the
* default constructor.
*
* DO NOT MODIFY THIS VARIABLE!
*/
public static final int INITIAL_CAPACITY = 13;
/*
* The max load factor of the ExternalChainingHashMap.
*
* DO NOT MODIFY THIS VARIABLE!
*/
public static final double MAX_LOAD_FACTOR = 0.67;
/*
* Do not add new instance variables or modify existing ones.
*/
private ExternalChainingMapEntry[] table;
private int size;
/**
* Constructs a new ExternalChainingHashMap with an initial capacity of INITIAL_CAPACITY.
*/
public ExternalChainingHashMap() {
//DO NOT MODIFY THIS METHOD!
table = (ExternalChainingMapEntry[]) new ExternalChainingMapEntry[INITIAL_CAPACITY];
}
/**
* Adds the given key-value pair to the map. If an entry in the map
* already has this key, replace the entry's value with the new one
* passed in.
*
* In the case of a collision, use external chaining as your resolution
* strategy. Add new entries to the front of an existing chain, but don't
* forget to check the entire chain for duplicate keys first.
*
* If you find a duplicate key, then replace the entry's value with the new
* one passed in. When replacing the old value, replace it at that position
* in the chain, not by creating a new entry and adding it to the front.
*
* Before actually adding any data to the HashMap, you should check to
* see if the table would violate the max load factor if the data was
* added. Resize if the load factor (LF) is greater than max LF (it is
* okay if the load factor is equal to max LF). For example, let's say
* the table is of length 5 and the current size is 3 (LF = 0.6). For
* this example, assume that no elements are removed in between steps.
* If another entry is attempted to be added, before doing anything else,
* you should check whether (3 + 1) / 5 = 0.8 is larger than the max LF.
* It is, so you would trigger a resize before you even attempt to add
* the data or figure out if it's a duplicate. Be careful to consider the
* differences between integer and double division when calculating load
* factor.
*
* When regrowing, resize the length of the backing table to
* (2 * old length) + 1. You should use the resizeBackingTable method to do so.
*
* @param key The key to add.
* @param value The value to add.
* @return null if the key was not already in the map. If it was in the
* map, return the old value associated with it.
* @throws java.lang.IllegalArgumentException If key or value is null.
*/
public V put(K key, V value) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
int hash = calculateHash(key, table.length);
// Create a new node with the new key-value pair
ExternalChainingMapEntry newNode = new ExternalChainingMapEntry(key, value);
// Check if the linked list at the given index is null
if (table[hash] == null) {
// If it's null, instantiate a new ExternalChainingMapEntry to represent the head
table[hash] = newNode;
size++;
if ((countEntries(table)) / table.length > MAX_LOAD_FACTOR) {
resizeBackingTable(table.length);
}
return null;
}
// Search through the linked list to find if the key already exists
ExternalChainingMapEntry current = table[hash];
while (current != null) {
if (current.getKey().equals(key)) {
// If the key already exists, replace the old value with the new value
current.setValue(value);
return null; // Key found and replaced, exit the entire method
}
current = current.getNext();
}
// Sets the "next" reference of the newNode to be the current head of the linked list at the specified index (table[hash]).
// It's saying, "the next element after this new node is the current head of the list."
// This way, you are linking the new node to the existing elements in the list.
newNode.setNext(table[hash]);
// Set the new node as the new head of the linked list at the specified index
table[hash] = newNode;
size++;
if ((countEntries(table)) / table.length > MAX_LOAD_FACTOR) {
resizeBackingTable(table.length);
}
return null;
}
/**
* Removes the entry with a matching key from the map.
*
* @param key The key to remove.
* @return The value associated with the key.
* @throws java.lang.IllegalArgumentException If key is null.
* @throws java.util.NoSuchElementException If the key is not in the map.
*/
public V remove(K key) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
if (key == null) {
throw new IllegalArgumentException("Error: key is null");
}
int hash = calculateHash(key, table.length);
if(table[hash] == null) {
throw new NoSuchElementException("Error: entry is empty");
}
ExternalChainingMapEntry current = table[hash];
ExternalChainingMapEntry prev = null;
while (current != null && !current.getKey().equals(key)) {
prev = current;
current = current.getNext();
}
if (current == null) {
throw new NoSuchElementException("Error: key not found");
}
V removedValue = current.getValue();
if (prev == null) {
// If the entry to be removed is the head of the linked list
table[hash] = current.getNext();
} else {
// If the entry to be removed is not the head of the linked list
prev.setNext(current.getNext());
}
size--; // Decrement size when removing an entry
return removedValue;
}
/**
* Helper method stub for resizing the backing table to length.
*
* This method should be called in put() if the backing table needs to
* be resized.
*
* You should iterate over the old table in order of increasing hash and
* add entries to the new table in the order in which they are traversed.
*
* Since resizing the backing table is working with the non-duplicate
* data already in the table, you won't need to explicitly check for
* duplicates.
*
* Hint: You cannot just simply copy the entries over to the new table.
*
* @param Length The new length of the backing table.
*/
private void resizeBackingTable(int length) {
// WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)!
ExternalChainingMapEntry[] newBackingArray = (ExternalChainingMapEntry[]) new ExternalChainingMapEntry[2 * length + 1];
for (ExternalChainingMapEntry entry : table) {
while (entry != null) {
int hash = calculateHash(entry.getKey(), newBackingArray.length);
ExternalChainingMapEntry next = entry.getNext();
entry.setNext(newBackingArray[hash]);
newBackingArray[hash] = entry;
entry = next;
}
}
table = newBackingArray;
}
//The hash function
private int calculateHash(K key, int array) {
if (key == null) {
throw new IllegalArgumentException("Error: key is null");
}
int hash = Math.abs(key.hashCode() % array);
return hash;
}
//Counts number of non-null entries in an array
private int countEntries(ExternalChainingMapEntry[] table) {
int count = 0;
for (int i = 0; i < table.length; i++) {
if (table[i] != null) {
count++;
}
}
return count;
}
/**
* Returns the table of the map.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return The table of the map.
*/
public ExternalChainingMapEntry[] getTable() {
// DO NOT MODIFY THIS METHOD!
return table;
}
/**
* Returns the size of the map.
*
* For grading purposes only. You shouldn't need to use this method since
* you have direct access to the variable.
*
* @return The size of the map.
*/
public int size() {
// DO NOT MODIFY THIS METHOD!
return size;
}
}
Подробнее здесь: https://stackoverflow.com/questions/779 ... a-hash-map
