4

次のデータ構造を使用するだけで、配列を使用して Hashtable を実装できました。

LinkedList<Item<K,V>> table[]
const int MAX_SIZE = 100

つまり、リンクされたリストの配列（連鎖によるハッシュ）。

現在、さまざまな本で、順序付けられたデータが必要な場合は、BST を使用してハッシュテーブルを実装できると述べています。キーと値の両方を BST に組み込むにはどうすればよいですか。単一のデータ項目を保存するのと同じように両方を保存できますが、キーは、ハッシュ関数に渡された後、配列へのインデックスのように機能する整数を与えます。BST でキーを使用するにはどうすればよいですか? インデックスは必要ありませんか？

私が考えることができるのは、関数を使用して2つのキーを比較し、それに応じて通常の挿入、削除を行うことができるということです.

編集:

BSTを最初から持っているとします

class Node {
        K key;
        V value;
        Node left;
        Node right;
    }


class BinarySearchTree {
            Node root;
        }


class Hashtable {

BinarySearchTree bst;

public void Hashtable() {
bst = new BinarySearchTree();
}

//hashfunction(K key)

//get(K Key)

//put(K key,V value)

//remove(K key)

}

整数にマップされたキーを使用して実装するにはどうすればよいですか

insert(V value)

BSTで。

4

4 に答える 4

2

java- TreeMapにはすでに BST の実装があります。それは自己バランスのとれた赤黒の木です。導入自体はさほど問題ないと思います。例えば：

public class Hashtable<T, V> implements Map<T, V> {

    private TreeMap<T, V> bst;

    public Hashtable() {
        bst= new TreeMap<T, V>();
    }

    @Override
    public void put(T element, V value) {
        bst.put(element, value);
    }

    ...

}

Hashtable はインターフェースの実装であるべきなので、実装することをおMap勧めしますjava.util.Map。継承ではなく構成によって BST を使用するので、BST の API を非表示にできます。BST は何でもかまいません。私のコード例では、Java のTreeMapクラスを使用しました。

于 2013-06-24T16:01:16.493 に答える
2

Java固有の回答はすでに提供されていますが、あなたの質問は言語固有の実装ではなく設計に関するものだと思います。

いいえ、インデックスを計算したり、ハッシュ関数を使用したりする必要はありません。キーと値のペアを bst のノードに格納すると、キーを比較してツリーをトラバースするだけです。これにより、キーが一意であるため、衝突が発生しないという追加の利点も得られます。

ハッシュ関数を使用してキーをハッシュし、その値に基づいてツリーをトラバースすることもできますが、ハッシュ関数に注意しないと衝突が発生する可能性があり、何らかの連鎖を維持する必要があります。

キーを使用するか、キーのハッシュ値を使用するかは、キーのサイズによって異なります。キーのサイズが大きい場合は、比較を高速化するために小さいサイズにハッシュするのが理にかなっています。

于 2015-10-24T16:11:51.337 に答える
0

リンク リストを使用してハッシュ テーブルを実装する必要はありません。O(n) を検索するのに線形時間がかかるチェーンを使用する代わりに衝突が発生した場合にのみ、バランスの取れた bst を使用して検索時間を O(log n) に短縮できます。

于 2014-09-04T07:59:28.220 に答える
0

BST をバケットとして使用した HashMap の簡単な実装を次に示します。この Map の基本的な実装は、put() と get() がどのように機能して、BST バケットに基づく Map からデータを取得するかを示しています。この BST 実装はバランスが取れていません。本番アプリケーションに理想的なのは、この BST を Red-Black ツリー アルゴリズムを使用してバランスを取り、シーク時間を改善することです。

リンクされたリストと比較してバランスの取れた BST を使用して実装されたバケットを使用すると、Get(key) 時間を O(n) から O(log n) に改善できます。

public class HashMapWithBST {

    private Node[] nodes;
    private static final int MAX_CAPACITY = 41;

    public HashMapWithBST() {
        nodes = new Node[MAX_CAPACITY];
    }

    /**
     * If key is a non-null object then return the hash code of key modulo hash map size as value. If key is null then return 0.
     * 
     * @param key
     * @return hash
     */
    public int getHash(String key) {

        if(key == null) {
            return 0;
        }

        int hash = key.hashCode();

        hash = hash >>> 16; // Spread the higher bits

        hash = hash % MAX_CAPACITY;

        return hash;
    }

    /**
     * In case of collisions, put the new key-value pair in a BST based on key comparisons.
     * 
     * @param key
     * @param value
     */
    public void put(String key, String value) {

        int hashOfKey = getHash(key);

        final Node newNode = new Node(key, value);

        if(nodes[hashOfKey] == null) {

            nodes[hashOfKey] = newNode;
        } else {

            Node root = nodes[hashOfKey];

            try {
                addToBSTBucket(root, newNode);
            } catch(Exception e ) {
                e.printStackTrace();
            }
        }

    }

    /**
     * If a collision happens while adding a node to Hashmap, add new node to the hashed bucket represented with a BST.
     * 
     * @param root      root of BST bucket
     * @param newNode   New Node to be added in BST bucket
     */
    private void addToBSTBucket(Node root, final Node newNode) {

        if(root == null) {
            root = newNode;
            return;
        }

        Node currentNode = root;
        Node parentNode = root;

        while(true) {

            parentNode = currentNode;

            if(newNode.key.compareTo(currentNode.key) == 0) {

                // if key values are same then just overwrite the vale in same node as duplicate keys are not allowed in this map
                currentNode.value = newNode.value;
                return;

            } else if(newNode.key.compareTo(currentNode.key) < 0) {
                currentNode = currentNode.left;

                if(currentNode == null) {
                    parentNode.left = newNode;
                    return;
                }
            } else {

                currentNode = currentNode.right;

                if(currentNode == null) {
                    parentNode.right = newNode;
                    return;
                }
            } 
        }

    }

    /**
     * Get the value for a particular key. If no key found then return null.
     * 
     * @param key
     * @return value or null
     */
    public String get(String key) {

        Node node = nodes[getHash(key)];

        if(node != null) {
            return getValueFromBST(node, key);
        }

        return null;
    }

    private String getValueFromBST(Node root, String key) {

        if(key == null) {
            return null;
        }

        while(root != null) {
            if(key.equals(root.key)) {
                return root.value;
            } else if(key.compareTo(root.key) < 0) {
                root = root.left;
            } else {
                root = root.right;
            }
        }

        return null;    
    }

    private static class Node {

        private String key;
        private String value;
        private Node left;
        private Node right;

        public Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

    }
}

完全なコードは次の場所にあります。

于 2016-02-11T15:20:56.203 に答える