java 如何使用二叉搜索树实现哈希表？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/17279805/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How do I implement a Hashtable using a Binary Search Tree?
提问by Hooli
I was able to implement Hashtable using array by simply using the following data structure.
通过简单地使用以下数据结构，我能够使用数组实现 Hashtable。
LinkedList<Item<K,V>> table[]
const int MAX_SIZE = 100
i.e an array of linked list(hashing with chaining).
即一个链表数组（链式散列）。
Now in various books,they say we can implement a hashtable with a BST if we want ordered data. How do I incorporate both key and value in a BST. Although I can store both just as I store a single item of data, but the key gives an integer that acts like an index to the array after it has been to a hash function. How do I use the key in BST? I don't need any index?
现在在各种书籍中，他们说如果我们想要有序数据，我们可以使用 BST 实现一个哈希表。如何在 BST 中同时包含键和值。虽然我可以像存储单个数据项一样存储两者，但是键给出了一个整数，在它进入散列函数后，它的作用类似于数组的索引。如何在 BST 中使用密钥？我不需要任何索引？
What I can think of is that I can compare two keys using the function and then do normal insertion,deletion accordingly.
我能想到的是我可以使用该功能比较两个键，然后相应地进行正常插入，删除。
EDITS:
编辑：
Suppose I have BST from scratch
假设我从头开始拥有 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)
}
How do I use the key mapped to integer to implement the
如何使用映射到整数的键来实现
insert(V value)
in BST.
在 BST。
回答by darijan
There is already an implementation of BST in java - TreeMap. It's a self balancing red-black tree. I guess implementing it would not be a much problem. For example:
在 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);
}
...
}
Since Hashtable should be implementation of Mapinterface, I suggest implementing java.util.Map. I would use a BST through composition rather than inheritance - so we can hide the API of the BST. The BST can be anything - in my code example I used Java's TreeMapclass.
由于Hashtable应该是Map接口的实现，我建议实现java.util.Map. 我会通过组合而不是继承来使用 BST - 所以我们可以隐藏 BST 的 API。BST 可以是任何东西——在我的代码示例中，我使用了 Java 的TreeMap类。
回答by pmathew
Java specific answers have already been provided but I am guessing your question is more about the design rather than language specific implementation.
已经提供了特定于 Java 的答案，但我猜您的问题更多是关于设计而不是特定于语言的实现。
No, we do not need to calculate an index or use a hashing function. If we store the key,value pairs in the nodes of the bst, then its just a matter of traversing the tree by comparing the keys. This also gives you the added advantage of no collisions since the keys are unique.
不，我们不需要计算索引或使用散列函数。如果我们将键值对存储在 bst 的节点中，那么它只是通过比较键来遍历树的问题。这也为您提供了无冲突的额外优势，因为键是唯一的。
You could use a hashing function and hash the key and then traverse the tree based on that value but this can lead to collisions if you are not careful with the hash function and then you would have to maintain some sort of chaining.
您可以使用散列函数并散列键，然后根据该值遍历树，但是如果您不小心使用散列函数，这可能会导致冲突，然后您将不得不维护某种链接。
Whether to use the key or the hashed value of the key depends on the size of the key. If the key size is large, it makes sense to hash it to a smaller size for faster comparison.
是使用密钥还是使用密钥的散列值取决于密钥的大小。如果密钥大小很大，则将其散列到较小的大小以进行更快的比较是有意义的。
回答by Prabhash Rathore
Here is a simple implementation of HashMap with BST as buckets. This basic implementation of Map shows how put() and get() works to get data from Map backed by BST buckets. This BST implementation is NOT balanced. Ideally for production applications, this BST should be balanced using Red-Black tree algorithm to improve seek time.
这是一个以 BST 作为存储桶的 HashMap 的简单实现。Map 的这个基本实现展示了 put() 和 get() 如何从 BST 存储桶支持的 Map 中获取数据。这个 BST 实现是不平衡的。理想情况下，对于生产应用程序，应该使用红黑树算法来平衡此 BST 以改善寻道时间。
With buckets implemented using balanced BST compared to Linked Lists, we are able to improve Get(key) time from O(n) to O(log n).
与链表相比，使用平衡 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;
}
}
}
The complete code is located here: https://github.com/prabhash1785/DataStructures/blob/d842d07e1fc3bf7e1caed72eb6b0744a719a9bc6/src/com/prabhash/java/algorithms/datastructures/HashMapWithBST.java
完整代码位于：https: //github.com/prabhash1785/DataStructures/blob/d842d07e1fc3bf7e1caed72eb6b0744a719a9bc6/src/com/prabhash/java/algorithms/datastructures/HashMapWithBST.java
回答by Vishal
You don't need to implement the hash table with link list. It's only the case when the collision happens instead of using chaining which takes linear time to search O(n) , you can use a balanced bst so that the search time reduces to O(log n).
您不需要使用链接列表来实现哈希表。仅当发生碰撞而不是使用需要线性时间来搜索 O(n) 的链接时，您可以使用平衡的 bst 以便搜索时间减少到 O(log n)。
