私は自分のHashMapを実装しなければならない割り当てに取り組んでいます。割り当てテキストでは、リストの配列として記述されており、要素を追加する場合は常に、配列内の最終的な場所はそのhashCodeによって決定されます。私の場合はスプレッドシートからの位置なので、columnNumber + rowNumberを取得し、それを文字列に変換してから、hashCodeとしてintに変換し、その場所を配列に挿入します。もちろん、Node（key、value）の形式で挿入されます。ここで、keyはセルの位置であり、valueはセルの値です。
しかし、なぜリストの配列が必要なのか理解できないと言わなければなりません。それは、複数の要素を含むリストになってしまった場合、ルックアップ時間が大幅に増えることはないのでしょうか。それで、それはむしろノードの配列であるべきではありませんか？
また、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]を調べ、それが空でなく、そこにあるものがキーを取得していない場合、putメソッドに入力されている場合、それはtable[に移動します。 （ハッシュ+ 1）％TABLE_SIZE]。ただし、同じキーの場合は、値が上書きされるだけです。それで、それは正しく理解されていますか？また、getメソッドとputメソッドは、配列内の場所を検索するのと同じメソッドを使用するため、同じキーを指定すると、配列内の同じ場所に配置されることになりますか？
これらの質問は少し基本的なものかもしれませんが、私はこれを整理するためにかなりの時間を費やしてきました。
編集
そこで、キーと対応する値を使用してノードを構築するだけのNodeクラスを介してHashMapを自分で実装しようとしました。また、getHashCodeメソッドもあり、2つの値を互いに連結します。
また、バケットとして使用する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）前後になるはずですが、そうなのか知りたいのですが。そうでなければ、その点でどうすればそれを改善できますか？