Mobile versionWenn das Hinzufügen zur Tabelle dazu führen würde, dass der Lastfaktor (LF) übersteigt (d. h. größer als, nicht größer als oder gleich) Wenn Sie die in der Java-Datei bereitgestellte Konstante für den maximalen Lastfaktor verwenden, sollte die Größe der Tabelle so geändert werden, dass sie eine Kapazität von 2n + 1 aufweist.
Ich versuche, die Größe auf 2n+1 zu ändern, wobei n ist die ursprüngliche Array-Größe. Aber es scheint aus irgendeinem Grund nicht zu funktionieren? Wann immer ich es teste, ändert sich die Größe des Arrays nie so, wie ich es möchte.
Ich glaube, das Problem könnte in einem dieser Codeteile liegen:
- Die Platzierung dieser Methode, die innerhalb der Put-Methode aufgerufen wird:
if ((countEntries(table)) / table.length > MAX_LOAD_FACTOR) {
resizeBackingTable(table.length);
} - Oder der Code innerhalb der resizeBackingTable-Methode selbst.
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 != 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;
}
}
Ich habe versucht, den Aufruf der resizeBackingTable an verschiedenen Stellen zu platzieren, aber es schien keine Wirkung zu haben. Ich hatte es auch schon ganz am Anfang der Put-Methode platziert, aber auch das hatte keine Auswirkung.