我正在做一个作业，我必须实现我自己的HashMap。在赋值文本中，它被描述为列表数组，每当你想要添加一个元素时，它在数组中的位置是由它的哈希代码决定的。就我而言，它是电子表格中的位置，所以我刚刚获取了列数 + 行数，然后将其转换为字符串，然后转换为整数，作为哈希代码，然后将其插入数组中的那个位置。它当然是以 Node（键，值）的形式插入的，其中键是单元格的位置，值是单元格的值。
但我必须说我不明白为什么我们需要一个列表数组，因为如果我们最终得到一个包含多个元素的列表，它不会大大增加查找时间吗？那么它不应该是一个节点数组吗？
我也在Java中发现了HashMap的实现：
public class HashEntry {
private int key;
private int value;
HashEntry(int key, int value) {
this.key = key;
this.value = value;
}
public int getKey() {
return key;
}
public int getValue() {
return value;
}
}
public class HashMap {
private final static int TABLE_SIZE = 128;
HashEntry[] table;
HashMap() {
table = new HashEntry[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = null;
}
public int get(int key) {
int hash = (key % TABLE_SIZE);
while (table[hash] != null && table[hash].getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
if (table[hash] == null)
return -1;
else
return table[hash].getValue();
}
public void put(int key, int value) {
int hash = (key % TABLE_SIZE);
while (table[hash] != null && table[hash].getKey() != key)
hash = (hash + 1) % TABLE_SIZE;
table[hash] = new HashEntry(key, value);
}
}
不为空，并且如果其中的内容没有获得键，则在方法 put 中输入，那么它移动到 table[（hash + 1） % TABLE_SIZE] 是否正确。但如果它是相同的键，它只会覆盖该值。那么理解正确吗？是不是因为 get 和 put 方法使用相同的方法来查找数组中的位置，给定相同的键，它们最终会在数组中的同一位置结束？
我知道这些问题可能有点基本，但我花了很多时间试图解决这个问题，为什么任何帮助将不胜感激！
编辑
所以现在我尝试通过 Node 类自己实现 HashMap，它只是构造一个带有键和相应值的节点，它还具有一个 getHashCode 方法，我只是将两个值相互连接。
我还构建了一个 SinglyLinkedList（之前作业的一部分），我将其用作存储桶。
我的哈希函数只是hashCode % hashMap.length。
这是我自己的实现，所以你怎么看？
package spreadsheet;
public class HashTableMap {
private SinglyLinkedListMap[] hashArray;
private int size;
public HashTableMap() {
hashArray = new SinglyLinkedListMap[64];
size = 0;
}
public void insert(final Position key, final Expression value) {
Node node = new Node(key, value);
int hashNumber = node.getHashCode() % hashArray.length;
SinglyLinkedListMap bucket = new SinglyLinkedListMap();
bucket.insert(key, value);
if(hashArray[hashNumber] == null) {
hashArray[hashNumber] = bucket;
size++;
}
if(hashArray[hashNumber] != null) {
SinglyLinkedListMap bucket2 = hashArray[hashNumber];
bucket2.insert(key, value);
hashArray[hashNumber] = bucket2;
size++;
}
if (hashArray.length == size) {
SinglyLinkedListMap[] newhashArray = new SinglyLinkedListMap[size * 2];
for (int i = 0; i < size; i++) {
newhashArray[i] = hashArray[i];
}
hashArray = newhashArray;
}
}
public Expression lookUp(final Position key) {
Node node = new Node(key, null);
int hashNumber = node.getHashCode() % hashArray.length;
SinglyLinkedListMap foundBucket = hashArray[hashNumber];
return foundBucket.lookUp(key);
}
}
查找时间应该在 O（1） 左右，所以我想知道是否是这种情况？如果没有，在这方面我该如何改进它？
你必须有一些计划来处理哈希冲突，其中两个不同的键落在同一个存储桶中，数组的相同元素。
最简单的解决方案之一是保留每个存储桶的条目列表。
如果你有一个很好的哈希算法，并确保桶的数量大于元素的数量，你最终应该得到大多数桶有零个或一个项目，所以列表搜索应该不会花费很长时间。如果列表太长，是时候重新使用更多存储桶来分散数据了。
这实际上取决于您的哈希码方法有多好。 假设你试图让它尽可能糟糕：你每次都让哈希码返回 1。 如果是这种情况，您将拥有一个列表数组，但数组中只有 1 个元素包含任何数据。 该元素只会增长到包含大量列表。
如果你这样做，你的哈希图就会非常低效。 但是，如果你的哈希代码好一点，它会将对象分布到许多不同的数组元素中，因此它会更有效率。
最理想的情况（通常无法实现）是拥有一个哈希码方法，无论您在其中放入什么对象，该方法都会返回一个唯一数字。 如果你能做到这一点，你就永远不需要一个列表数组了。 你可以只使用数组。 但是由于您的哈希代码并不"完美"，因此两个不同的对象可能具有相同的哈希代码。 您需要能够通过将它们放在同一数组元素的列表中来处理这种情况。
但是，如果你的哈希码方法"相当不错"并且很少发生冲突，那么你的列表中很少有超过 1 个元素。
Lists通常被称为桶，是一种处理碰撞的方法。 当两个数据元素具有相同的哈希代码 mod TABLE SIZE 时，它们会发生冲突，但必须存储它们。
更糟糕的冲突是两个不同的数据点具有相同的key - 这在哈希表中是不允许的，其中一个将覆盖其他数据点。 如果只是将行添加到列，则 （2,1） 和 （1,2） 的键均为 3，这意味着它们不能存储在同一个哈希表中。 如果您在没有分隔符的情况下将字符串连接在一起，那么问题出在 （12,1） 与 （1， 21） ---两者都有键"121"使用分隔符（例如逗号），所有键都将是不同的。
如果哈希代码是相同的 mod TABLE_SIZE，则不同的键可以落在同一个降压中。 这些列表是在同一存储桶中存储两个值的一种方法。
class SpreadSheetPosition {
int column;
int row;
@Override
public int hashCode() {
return column + row;
}
}
class HashMap {
private Liat[] buckets = new List[N];
public void put(Object key, Object value) {
int keyHashCode = key.hashCode();
int bucketIndex = keyHashCode % N;
...
}
}
比较有 N 个列表，只有一个列表/数组。要在列表中搜索，必须遍历整个列表。通过使用列表数组，至少可以减少单个列表。甚至可能获得一个或零个元素的列表（null）。
如果hashCode()尽可能独特，则立即找到的机会很高。