如何使用二叉搜索樹實現散列表？

我能夠通過簡單地使用以下數據結構來實現使用數組的Hashtable。如何使用二叉搜索樹實現散列表？

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

即鏈表（鏈接散列）。

現在在各種書籍中，他們說如果我們需要有序數據，我們可以用BST實現散列表。如何在BST中同時包含密鑰和值。雖然我可以存儲兩者，就像我存儲單個數據項一樣，但密鑰給出了一個整數，它在散列函數之後就像數組的索引一樣。我如何在BST中使用密鑰？我不需要任何索引？

我能想到的是，我可以使用該功能比較兩個鍵，然後相應地進行正常插入，刪除。

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

。

來源

2013-06-24 Hooli

我很新的節目，但不能使用一個樹狀圖呢？ http://stackoverflow.com/questions/13373854/binary-search-tree-java-implementation – spuder

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

來源

2013-06-24 16:01:16 darijan

我認爲這個問題是關於如何實現這個練習，而不是你在生產中做什麼。 –

是的，我希望實現它。我知道Java中的SortedMap。 – Hooli

此代碼如何關聯？說明。（5分） – zEro

您不需要使用鏈接列表實現哈希表。只有當發生碰撞而不是使用需要線性時間來搜索O（n）的鏈接時，可以使用平衡的bst，以便搜索時間縮短到O（log n）。

來源

2014-09-04 07:59:28 Vishal

已經提供了Java特定的答案，但我猜你的問題更多的是關於設計而不是語言特定的實現。

不，我們不需要計算索引或使用哈希函數。如果我們在bst的節點中存儲鍵值對，那麼它只是通過比較鍵來遍歷樹。這也爲您提供了無衝突的附加優勢，因爲這些按鍵是唯一的。

您可以使用散列函數並散列密鑰，然後遍歷基於該值的樹，但如果您不小心使用散列函數，則可能導致衝突，然後您必須維護某種鏈接。

是否使用密鑰或密鑰的哈希值取決於密鑰的大小。如果密鑰大小較大，則將其散列爲較小的大小以便進行更快速的比較是有意義的。

來源

2015-10-24 16:11:51 pmathew

這裏是以BST作爲桶的HashMap的簡單實現。 Map的這個基本實現展示了put（）和get（）如何工作從BST桶支持的Map中獲取數據。這個BST實現不平衡。對於生產應用來說理想的是，這個BST應該使用紅黑樹算法來平衡，以提高尋道時間。我們能夠將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

來源

2016-02-11 15:20:56

傳播更高位的目的是什麼？ 'hash = hash >>> 16; //傳播更高的位數不會實質上將任何少於約100,000的數字歸零？ –

如何使用二叉搜索樹實現散列表？

回答

相關問題