如何使用二分搜索树实现哈希表? [英] How do I implement a Hashtable using a Binary Search Tree?

问题描述

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

I was able to implement Hashtable using array by simply using the following data structure.

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

即链接列表的数组(通过链式哈希处理).

i.e an array of linked list(hashing with chaining).

现在，在各种书籍中，他们说如果我们想要有序的数据，我们可以使用BST来实现哈希表. 如何在BST中同时包含键和值.尽管我可以像存储单个数据一样存储这两个数据，但是键提供了一个整数，该整数在使用哈希函数后就像数组的索引一样工作.如何在BST中使用密钥?我不需要任何索引吗?

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?

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

What I can think of is that I can compare two keys using the function and then do normal insertion,deletion accordingly.

假设我从头开始拥有BST

Suppose I have BST from scratch

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) 

在BST中.

推荐答案

Java中已经存在BST的实现-

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:

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

Since Hashtable should be implementation of Map interface, 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 TreeMap class.

这篇关于如何使用二分搜索树实现哈希表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！