HashTable に関する質問です
解決済
回答 1
投稿
- 評価
- クリップ 0
- VIEW 597

退会済みユーザー
前提・実現したいこと
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;
}
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+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.
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう!
- ただいまの回答率 88.21%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
質問への追記・修正、ベストアンサー選択の依頼
swordone
2018/08/05 18:14
今更思ったが、キー重複の処理は?
退会済みユーザー
2018/08/06 08:27
キーの重複を解消できてないということでしょうか?確認してみます、、