0

ハッシュ テーブルのサイズを 2 倍にする方法がわかりません。コードは次のとおりです。

private void doubleLength () {
  //Remember the old hash table array and allocate a new one 2 times as big

  HashMap<K,V> resizedMap = new HashMap<K,V>(map.length * 2);

/*Traverse the old hash table adding each value to the new hash table.
 Instead, add it to by applying
 hashing/compression again (compression will be DIFFERENT, because the
 length of the table is doubled, so we compute the same hash value but
 compute the remainder using the DIFFERENT TABLE LENGTH).*/
   for (int i = 0; i < map.length; i++) {
        for (K key : map[i].entry) { //iterator does not work here
                    resizedMap.put(key, map[i].get(key)); //should go here
    }

}

ハッシュ テーブルは、LN オブジェクトの配列であり、LN は次のように定義されます。

public static class LN<K1,V1> {
   public Map.Entry<K1,V1> entry;
   public LN<K1,V1>        next;

   public LN (Map.Entry<K1,V1> e, LN<K1,V1> n)
   {entry = e; next = n;}
}

クラス内にイテラブルがありますが、map[i].entry.entries() は許可されません。

public Iterable<Map.Entry<K,V>> entries () {
return new Iterable<Map.Entry<K,V>>() {
  public Iterator<Map.Entry<K,V>> iterator() {
    return new MapEntryIterator();
  }
};
}

パブリック LN[] マップのサイズを 2 倍にする方法について非常に迷っています。

4

2 に答える 2

3

ハッシュ テーブルがいっぱいになると、はHashMapすでにサイズを変更しています。サイズを変更する必要はありません。

于 2012-11-16T20:07:19.067 に答える
0

コードはコンパイルされません。マップを初期化してサイズを 2 倍にしたい場合は、これを行う方が簡単です (もmapであると仮定しMapます)。

private void doubleLength () {
  //Remember the old hash table array and allocate a new one 2 times as big
  HashMap<K,V> resizedMap = new HashMap<K,V>(map.size()* 2);
  resizedMap.putAll(map);
}

また、あなたは奇妙なことにアクセスしているようです。マップをループする必要がある場合は、次のようになります。

for (K key : map.keySet()){
  V value = map.get(key); //get the value from the map
  //do what you need to do
}

すでに述べたように、HashMap のサイズを変更する必要はありません。すでにそれを行っています。JavaDocsから:

HashMap のインスタンスには、そのパフォーマンスに影響を与える 2 つのパラメーターがあります。それは、初期容量と負荷係数です。容量はハッシュ テーブル内のバケットの数であり、初期容量は単にハッシュ テーブルが作成された時点の容量です。負荷率は、容量が自動的に増加する前に、ハッシュ テーブルがどれだけいっぱいになることができるかの尺度です。ハッシュ テーブルのエントリ数が負荷係数と現在の容量の積を超えると、ハッシュ テーブルが再ハッシュされ (つまり、内部データ構造が再構築され)、ハッシュ テーブルのバケット数が約 2 倍になります。

于 2012-11-16T20:09:20.653 に答える