HashTable に関する質問です

Question

前提・実現したいこと

HashTable の #keys(key を全て取り出したい) と #loadFactor(bucket のサイズの平均値を求めたい)を実装したいのですが、どうすればよいのかさっぱり分かりません。アイデアを頂けないでしょうか？

HashTableEntry

public class HashTableEntry<K, V> {

    private K key;
    private V value;
    private int hash;

    public HashTableEntry(K key, V value) {
        if (key == null)
            throw new IllegalArgumentException("key cannot be null");

        this.key = key;
        this.value = value;
        this.hash = key.hashCode();
    }

    public K getKey() {
        return this.key;
    }

    public V getValue() {
        return this.value;
    }

    public int getHashCode() {
        return this.hash;
    }

    public String toString() {
        return "{" + key + ": " + value + " (" + hash + ")}";
    }

}

HashTable

import java.util.List;
import java.util.LinkedList;
import java.util.Arrays;


public class HashTable<K, V> {

    private Object[] entries;

    private List<HashTableEntry<K, V>> bucket(int i) {
        return (List<HashTableEntry<K, V>>)entries[i];
    }

    public HashTable(int numBuckets) {
        if (numBuckets < 1)
            throw new IllegalArgumentException("hash table must have at least one bucket");
        this.entries = new Object[numBuckets];
        for (int i = 0; i < numBuckets; i++)
            this.entries[i] = new LinkedList<HashTableEntry<K, V>>();
    }

    public void put(K key, V value) {
        HashTableEntry<K, V> e = new HashTableEntry<K, V>(key, value);
        int h = e.getHashCode();
        int b = Math.abs(h % this.entries.length);
        bucket(b).add(e);
    }

    public V get(K key) {
        int h = key.hashCode();
        int b = Math.abs(h % this.entries.length);
        for (HashTableEntry<K, V> e : bucket(b))
            if (key.equals(e.getKey()))
                return e.getValue();
        return null;
    }

    public List<K> keys() {
        List<K> klist = new LinkedList<K>();
    }

    public double loadFactor() {
        double sum = 0;
    }

Comments

[swordone]

今更思ったが、キー重複の処理は？

[退会済みユーザー]

キーの重複を解消できてないということでしょうか？確認してみます、、

Answer 1

全要素の列挙

拡張for文でHashTable#entriesを回して、回した要素のLinkedListをループでたどればいいのでは。

loadFactorもループでまわす部分は一緒ですが、LinkedList#size()を使って計算する部分が違います。

◇余談
HashTableEntryのKeyはインプレース変更を防止するために、インスタンス変数はfinalで宣言してくださいな。

---

どうすればすべて取り出せるでしょうか

パフォーマンスを気にしないのであれば以下のように。
2重ループでまわすコードです。(未テストです)

	public List<K> keys() {
		List<K> klist = new LinkedList<K>();
		for (int i = 0; i < this.entries.length; i++) {
			List<K> list = (List<K>) entries[i];
			for(int j=0;j < list.size();j++) {
				klist.add(list.get(j));
			}
		}
		return klist;
	}

以下からはパフォーマンスを気にする人向けのコード。
java.util.List#addAllを使うと、コレクションの要素をShallow Copy(※)できます。
※最初の回答もそうですが、Shallow Copyな点に注意

	List<K> list = (List<K>) entries[i];
-	for(int j=0;j < list.size();i++) {
-		klist.add(list.get(j));
-	}
+	klist.addAll(list);

次に質問文のコードはLinkedListなので、RandomAccessができません。
内部はArrayListで持つほうがよいでしょう。
◇参考情報
軽い気持ちでLinkedListを使ったら休出する羽目になった話

最後にもっとパフォーマンスを気にするのであれば、entriesとは別にhashcode値のみを管理するint配列(buckets)を宣言してloadFactorに応じてrehashしてくださいな。
あと多分スルーされたと思いますが、キーのインプレース変更も防止してくださいな。
個人的にライブラリのHashMapを使わずにHashTableを再実装される方の義務だと思っているので・・・

◇参考になりそうな物
.netのHashSetクラスのAddIfNotPresentをreferencesourceで見ると
※referencesourceのソースコードライセンスはMITです。

License
The files in this repository are licensed with the MIT license unless otherwise specified in the file header.

Comments

[退会済みユーザー]

ありがとうございます！以下のようになりました
```
public List<K> keys() {
List<K> klist = new LinkedList<K>();
for (int i = 0; i < this.entries.length; i++) {
klist = this.entries[i];
}
return klist;
}
```

```
public double loadFactor() {
double sum = 0;
for (int i = 0; i < this.entries.length; i++) {
sum += this.entries[i].size();
return sum / this.entries.length;
}
```

[umyu]

@egusaさんへ
そのkeys()ではfor文で毎回上書きしているので、最後のエントリーの内容しか取れてないです。
this.entries[i]の内容に対してもループするようにしてくださいな。

[退会済みユーザー]

確かに、数字を入れ替えるだけになってました。ありがとうございます！

[退会済みユーザー]

すいません、どうすればすべて取り出せるでしょうか？考えたんですが、分かりませんでした、、
コンパイルエラーが出るところもあり、多少修正しております

public List<K> keys() {
List<K> klist = new LinkedList<K>();
for (int i = 0; i < this.entries.length; i++) {
klist = (List<K>)entries[i];
}
return klist;
}

[退会済みユーザー]

@umyuさん
本当にありがとうございます！おかげ様でしっかりと理解することができました。
貼って頂いたものも、参考にさせてもらいます