1

チェーンとダブルプローブを比較しようとしています。40 個の整数をテーブル サイズ 100 に挿入する必要があります。ナノタイム (Java で) を使用して時間を測定すると、Double の方が高速であることがわかります。それは Chaining の Insert 方式で、毎回 LinkedListEntry を作成し、それが add 時間だからです。Chaining が Double probing よりも速いのはどうしてでしょうか? （それは私がウィキペディアで読んだものです）

ありがとう！！

これは連鎖のコードです：

public class LastChain
{
    int tableSize;
     Node[] st;
    LastChain(int size) {
        tableSize = size;
        st = new Node[tableSize];
        for (int i = 0; i < tableSize; i++)
            st[i] = null;
    }

    private class Node
    {
        int key;
        Node next;
        Node(int key, Node next)
        {
            this.key   = key;
            this.next  = next;
        }
    }

    public void put(Integer key) 
    {
       int i = hash(key);
       Node first=st[i];
       for (Node x = st[i]; x != null; x = x.next)
          if (key.equals(x.key))
             { 
             return; 
              }

       st[i] = new Node(key, first);

    }


    private int hash(int key)
    {  return key%tableSize;
    }

      }
}

これは、二重プローブからの関連コードです。

public class HashDouble1 {
  private Integer[] hashArray; 

  private int arraySize;

  private Integer bufItem; // for deleted items

  HashDouble1(int size) {
    arraySize = size;
    hashArray = new Integer[arraySize];
    bufItem = new Integer(-1);
  }



  public int hashFunc1(int key) {
    return key % arraySize;
  }

  public int hashFunc2(int key) {
    return 7 - key % 7;
  }

  public void insert(Integer key) {
        int hashVal = hashFunc1(key); // hash the key
        int stepSize = hashFunc2(key); // get step size
        // until empty cell or -1
        while (hashArray[hashVal] != null && hashArray[hashVal] != -1) {
          hashVal += stepSize; // add the step
          hashVal %= arraySize; // for wraparound
        }
        hashArray[hashVal]  = key; // insert item
      }





}

このように、Double での挿入は連鎖よりも高速です。どうすれば修正できますか？

4

2 に答える 2

1

連鎖は、負荷率が高い場合に最適に機能します。100 個のテーブルで 90 個の文字列 (整数の適切な配置ではありません) を使用しようとしています。

また、連鎖は削除/削除の実装がはるかに簡単です。

注: HashMap では、チェーン化されているかどうかに関係なく Entry オブジェクトが作成されますが、そこには保存されません。

于 2012-12-12T12:25:43.763 に答える
0

Java には特別な「機能」があります オブジェクトは多くのメモリを占有します。

したがって、大規模なデータセット (関連性がある場合) では、ダブルプローブが適しています。

しかし、最初に Integer[] を int[] に変更してください -> メモリ使用量は 4 分の 1 程度になり、パフォーマンスは飛躍的に向上します。

ただし、常にパフォーマンスの問題があります。測定、測定、測定、あなたのケースは常に特別です。

于 2012-12-12T12:48:33.400 に答える