如何使用二叉搜索树实现哈希表？

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)

}

如何使用映射到整数的键来实现

此问题需要更多上下文和信息才能明确。请提供更多细节。

insert(V value) 

在二叉搜索树中。

- Hooli

---

我对编程还比较新，但是你不能使用树图吗？https://dev59.com/NWYr5IYBdhLWcg3w0tWE - spuder

Answer 1

已经提供了与Java相关的解答，但我猜你的问题更多关于设计而非语言的具体实现。

不需要计算索引或使用哈希函数。如果我们把键值对存储在bst的节点中，那么只需通过比较键来遍历树。这还给您带来了额外的优势，因为键是唯一的，所以不会发生冲突。

您可以使用哈希函数对键进行哈希处理，然后基于该值遍历树，但如果您对哈希函数不小心，这可能会导致冲突，那么您就必须维护某种形式的链接。

是否使用键还是键的哈希值取决于键的大小。如果键的大小很大，则将其哈希成较小的大小以进行更快的比较是有意义的。

- pmathew

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

- darijan

---

我认为这个问题是关于如何将其作为练习实现，而不是在生产环境中该怎么做。 - Tom Hawtin - tackline

是的，我希望实现它。我知道Java中的SortedMap。 - Hooli

根据JDK文档，Dictionary类已经过时。在实现自定义HashMap时，我们应该使用Map接口。 - Prabhash Rathore

谢谢@PrabhashRathore，我已经修复了它。 - darijan

Answer 3

这是一个使用二叉搜索树作为桶的HashMap的简单实现。这个基本的Map实现展示了如何使用put()和get()从由BST桶支持的Map中获取数据。这个BST实现是不平衡的。理想情况下，对于生产应用程序，应该使用红黑树算法平衡这个BST以提高查找时间。

使用平衡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;
        }

    }
}

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

- Prabhash Rathore

---

扩散高位的目的是什么？hash = hash >>> 16; // Spread the higher bits 这样做不会将小于100,000的数字归零吗？ - Ryan Quinn

Answer 4

你不需要使用链表实现哈希表。只有在发生冲突的情况下才会出现这种情况，而使用链接需要线性时间搜索O(n)，你可以使用平衡二叉树来减少搜索时间到O(log n)。

- Vishal