如何使用二进制搜索树实现哈希表

Question

我只需使用以下数据结构就可以使用数组实现Hashtable。

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

即链表的数组（通过链接进行散列）。

现在在各种书中，他们说如果我们想要有序的数据，我们可以用BST实现哈希表。如何在BST中合并键和值。虽然我可以像存储单个数据项一样存储这两个数据项，但键在到达哈希函数后会给出一个整数，其作用就像数组的索引。如何在BST中使用密钥？我不需要任何索引？

我能想到的是，我可以使用该功能比较两个键，然后相应地进行正常的插入和删除。

编辑：

假设我有从头开始的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)
}

如何使用映射到integer的密钥来实现

insert(V value) 

在BST.

Answer 1

已经提供了特定于Java的答案，但我猜您的问题更多地是关于设计，而不是特定于语言的实现。

不，我们不需要计算索引或使用哈希函数。如果我们将键、值对存储在bst的节点中，那么这只是通过比较键来遍历树的问题。这也为您提供了无碰撞的额外优势，因为关键帧是唯一的。

你可以使用哈希函数对密钥进行哈希，然后根据该值遍历树，但如果你不小心使用哈希函数，这可能会导致冲突，然后你将不得不维护某种链接。

是使用密钥还是使用密钥的哈希值取决于密钥的大小。如果密钥大小较大，则将其散列为较小的大小以进行更快的比较是有意义的。

Answer 2

在java中已经有了BST的实现-TreeMap。这是一棵自我平衡的红黑树。我想实现它不会有太大问题。例如：

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类。

Answer 3

您不需要实现带有链表的哈希表。只有当发生冲突时，才可以使用平衡的bst来减少搜索时间，而不是使用需要线性时间来搜索O（n）的链接。

Answer 4

这里是一个简单的HashMap实现，使用BST作为bucket。Map的这个基本实现展示了put（）和get（）如何从BST桶支持的Map中获取数据。此BST实施不平衡。理想情况下，对于生产应用程序，应该使用红黑树算法来平衡此BST，以提高寻道时间。

与链表相比，使用平衡BST实现的bucket，我们能够将Get（key）时间从O（n）提高到O（logn）。

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;
        }
    }
}

完整的代码位于此处：https://github.com/prabhash1785/DataStructures/blob/d842d07e1fc3bf7e1caed72eb6b0744a719a9bc6/src/com/prabhash/java/algorithms/datastructures/HashMapWithBST.java