如何使用二叉搜索树实现Hashtable？
通过简单地使用以下数据结构，我能够使用数组实现Hashtable。
LinkedList<Item> table[] const int MAX_SIZE = 100 即链表列表（带链接的散列）。
现在在各种书中，他们说如果我们想要有序数据，我们可以用BST实现哈希表。 如何在BST中包含键和值。 虽然我可以像存储单个数据项一样存储这两个数据，但是键给出了一个整数，它就像一个散列函数之后的数组索引。 如何在BST中使用密钥？ 我不需要任何索引？
我能想到的是我可以使用该function比较两个键，然后相应地进行正常插入和删除。
EDITS：
假设我从头开始有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。
已经提供了Java特定的答案，但我猜你的问题更多的是关于设计而不是语言特定的实现。
不，我们不需要计算索引或使用散列函数。 如果我们在bst的节点中存储键值对，那么只需通过比较键来遍历树。 这也为您提供了无冲突的额外优势，因为密钥是唯一的。
您可以使用散列函数并对密钥进行散列，然后根据该值遍历树，但如果您不小心使用散列函数，则可能会导致冲突，然后您必须保持某种链接。
是否使用密钥或密钥的散列值取决于密钥的大小。 如果密钥大小很大，则将其散列为较小的大小以便更快地进行比较是有意义的。
在Java – TreeMap中已经有了BST的实现。 这是一种自平衡的红黑树。 我想实现它不会是一个太大的问题。 例如：
public class Hashtable implements Map { private TreeMap bst; public Hashtable() { bst= new TreeMap(); } @Override public void put(T element, V value) { bst.put(element, value); } ... }
由于Hashtable应该是Map接口的实现，我建议实现java.util.Map 。 我会通过组合而不是inheritance来使用BST – 所以我们可以隐藏BST的API。 BST可以是任何东西 – 在我的代码示例中，我使用了Java的TreeMap类。
您不需要使用链接列表实现哈希表。 只有当碰撞发生而不是使用线性时间搜索O（n）的链接时，才能使用平衡的bst，以便搜索时间减少到O（log n）。
以下是使用BST作为存储桶的HashMap的简单实现。 Map的这个基本实现显示了put（）和get（）如何工作以从BST桶支持的Map获取数据。 此BST实施不平衡。 理想情况下，对于生产应用程序，应使用红黑树算法来平衡此BST，以缩短查找时间。
使用平衡BST与链接列表相比实现存储桶，我们能够将Get（密钥）时间从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