如何在java中實現可擴展哈希？

Question

可擴展哈希是最好的哈希方法之一，我想在java中創建程序，用於可擴展哈希。有沒有可用的API？我沒有得到明確的算法自己做，所以如果沒有api，.if如果可能的話後algoirhtm

Answer 1

前言：我不知道什麼是可擴展哈希。

根據我對這個wiki的瞭解（http://en.wikipedia.org/wiki/Extendible_hashing），它可以使用最多兩次查找進行搜索，您可能需要查看Bernstein DB（sg-cDB）的Java實現。 http://cr.yp.to/cdb.html

Answer 2

我只是好奇，爲什麼你需要實現這樣的算法？標準Java Map實現是否不適合您？如果您正在遭遇桶變得負載過重的問題，您可能需要在選擇非標準路由之前查看hashCode（）方法。另一種選擇也可以看看GNU Trove提供的一些選項。

最後 - 與Extendible類似的算法是杜鵑哈希。下面的一些信息：

http://en.wikipedia.org/wiki/Cuckoo_hashing

源代碼在這裏：

http://lmonson.com/blog/?page_id=99

Answer 3

Java實現可擴展的hash值： http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables#A_Java_implementation_of_extendible_hashing

由於srini.venigalla說的...伯恩斯坦的sg-cDB很好。您可以在GitHub中找到由Michael Alyn Miller製作的純Java版CDB：https://github.com/malyn/sg-cdb

Answer 4

此文件定義了一個HashTable類。散列表 中的鍵和值的類型爲Object。鍵不能爲空。默認的構造函數 創建一個表，最初有64個位置，但不同的初始大小可以指定爲構造函數的參數。 如果表格大於3/4，表格會增加。

public class HashTable { 

    static private class ListNode { 
     // Keys that have the same hash code are placed together 
     // in a linked list. This private nested class is used 
     // internally to implement linked lists. A ListNode 
     // holds a (key,value) pair. 
    Object key; 
    Object value; 
    ListNode next; // Pointer to next node in the list; 
        // A null marks the end of the list. 
    } 

    private ListNode[] table; // The hash table, represented as 
          // an array of linked lists. 

    private int count; // The number of (key,value) pairs in the 
         // hash table. 

    public HashTable() { 
     // Create a hash table with an initial size of 64. 
    table = new ListNode[64]; 
    } 

    public HashTable(int initialSize) { 
     // Create a hash table with a specified initial size. 
     // Precondition: initalSize > 0. 
    table = new ListNode[initialSize]; 
    } 

    void dump() { 
     // This method is NOT part of the usual interface for 
     // a hash table. It is here only to be used for testing 
     // purposes, and should be removed before the class is 
     // released for general use. This lists the (key,value) 
     // pairs in each location of the table. 
    System.out.println(); 
    for (int i = 0; i < table.length; i++) { 
      // Print out the location number and the list of 
      // key/value pairs in this location. 
     System.out.print(i + ":"); 
     ListNode list = table[i]; // For traversing linked list number i. 
     while (list != null) { 
      System.out.print(" (" + list.key + "," + list.value + ")"); 
      list = list.next; 
     } 
     System.out.println(); 
    } 
    } // end dump() 

    public void put(Object key, Object value) { 
     // Associate the specified value with the specified key. 
     // Precondition: The key is not null. 
    int bucket = hash(key); // Which location should this key be in? 
    ListNode list = table[bucket]; // For traversing the linked list 
            // at the appropriate location. 
    while (list != null) { 
      // Search the nodes in the list, to see if the key already exists. 
     if (list.key.equals(key)) 
      break; 
     list = list.next; 
    } 
     // At this point, either list is null, or list.key.equals(key). 
    if (list != null) { 
      // Since list is not null, we have found the key. 
      // Just change the associated value. 
     list.value = value; 
    } 
    else { 
      // Since list == null, the key is not already in the list. 
      // Add a new node at the head of the list to contain the 
      // new key and its associated value. 
     if (count >= 0.75*table.length) { 
      // The table is becoming too full. Increase its size 
      // before adding the new node. 
      resize(); 
     } 
     ListNode newNode = new ListNode(); 
     newNode.key = key; 
     newNode.value = value; 
     newNode.next = table[bucket]; 
     table[bucket] = newNode; 
     count++; // Count the newly added key. 
    } 
    } 

    public Object get(Object key) { 
     // Retrieve the value associated with the specified key 
     // in the table, if there is any. If not, the value 
     // null will be returned. 
    int bucket = hash(key); // At what location should the key be? 
    ListNode list = table[bucket]; // For traversing the list. 
    while (list != null) { 
      // Check if the specified key is in the node that 
      // list points to. If so, return the associated value. 
     if (list.key.equals(key)) 
      return list.value; 
     list = list.next; // Move on to next node in the list. 
    } 
     // If we get to this point, then we have looked at every 
     // node in the list without finding the key. Return 
     // the value null to indicate that the key is not in the table. 
    return null; 
    } 

    public void remove(Object key) { 
     // Remove the key and its associated value from the table, 
     // if the key occurs in the table. If it does not occur, 
     // then nothing is done. 
    int bucket = hash(key); // At what location should the key be? 
    if (table[bucket] == null) { 
      // There are no keys in that location, so key does not 
      // occur in the table. There is nothing to do, so return. 
     return; 
    } 
    if (table[bucket].key.equals(key)) { 
      // If the key is the first node on the list, then 
      // table[bucket] must be changed to eliminate the 
      // first node from the list. 
     table[bucket] = table[bucket].next; 
     count--; // Remove new number of items in the table. 
     return; 
    } 
     // We have to remove a node from somewhere in the middle 
     // of the list, or at the end. Use a pointer to traverse 
     // the list, looking for a node that contains the 
     // specified key, and remove it if it is found. 
    ListNode prev = table[bucket]; // The node that precedes 
            // curr in the list. Prev.next 
            // is always equal to curr. 
    ListNode curr = prev.next; // For traversing the list, 
           // starting from the second node. 
    while (curr != null && ! curr.key.equals(key)) { 
     curr = curr.next; 
     prev = curr; 
    } 
     // If we get to this point, then either curr is null, 
     // or curr.key is equal to key. In the later case, 
     // we have to remove curr from the list. Do this 
     // by making prev.next point to the node after curr, 
     // instead of to curr. If curr is null, it means that 
     // the key was not found in the table, so there is nothing 
     // to do. 
    if (curr != null) { 
     prev.next = curr.next; 
     count--; // Record new number of items in the table. 
    } 
    } 

    public boolean containsKey(Object key) { 
     // Test whether the specified key has an associated value 
     // in the table. 
    int bucket = hash(key); // In what location should key be? 
    ListNode list = table[bucket]; // For traversing the list. 
    while (list != null) { 
      // If we find the key in this node, return true. 
     if (list.key.equals(key)) 
      return true; 
     list = list.next; 
    } 
     // If we get to this point, we know that the key does 
     // not exist in the table. 
    return false; 
    } 

    public int size() { 
     // Return the number of key/value pairs in the table. 
    return count; 
    } 

    private int hash(Object key) { 
     // Compute a hash code for the key; key cannot be null. 
     // The hash code depends on the size of the table as 
     // well as on the value returned by key.hashCode(). 
    return (Math.abs(key.hashCode())) % table.length; 
    } 

    private void resize() { 
     // Double the size of the table, and redistribute the 
     // key/value pairs to their proper locations in the 
     // new table. 
    ListNode[] newtable = new ListNode[table.length*2]; 
    for (int i = 0; i < table.length; i++) { 
      // Move all the nodes in linked list number i 
      // into the new table. No new ListNodes are 
      // created. The existing ListNode for each 
      // key/value pair is moved to the newtable. 
      // This is done by changing the "next" pointer 
      // in the node and by making a pointer in the 
      // new table point to the node. 
     ListNode list = table[i]; // For traversing linked list number i. 
     while (list != null) { 
       // Move the node pointed to by list to the new table. 
      ListNode next = list.next; // The is the next node in the list. 
             // Remember it, before changing 
             // the value of list! 
      int hash = (Math.abs(list.key.hashCode())) % newtable.length; 
       // hash is the hash code of list.key that is 
       // appropriate for the new table size. The 
       // next two lines add the node pointed to by list 
       // onto the head of the linked list in the new table 
       // at position number hash. 
      list.next = newtable[hash]; 
      newtable[hash] = list; 
      list = next; // Move on to the next node in the OLD table. 
     } 
    } 
    table = newtable; // Replace the table with the new table. 
    } // end resize() 

} // end class HashTable 

一個程序測試哈希表：
一個小程序來測試Hashtable類。請注意，我從一個非常小的表開始，以便可以輕鬆測試resize（）方法。

public class TestHashTable { 

    public static void main(String[] args){ 
    HashTable table = new HashTable(2); 
    String key,value; 
    while (true) { 
     System.out.println("\nMenu:"); 
     System.out.println(" 1. test put(key,value)"); 
     System.out.println(" 2. test get(key)"); 
     System.out.println(" 3. test containsKey(key)"); 
     System.out.println(" 4. test remove(key)"); 
     System.out.println(" 5. show complete contents of hash table."); 
     System.out.println(" 6. EXIT"); 
     System.out.print("Enter your command: "); 
     switch (TextIO.getlnInt()) { 
      case 1: 
       System.out.print("\n Key = "); 
       key = TextIO.getln(); 
       System.out.print(" Value = "); 
       value = TextIO.getln(); 
       table.put(key,value); 
       break;   
      case 2: 
       System.out.print("\n Key = "); 
       key = TextIO.getln(); 
       System.out.println(" Value is " + table.get(key)); 
       break;   
      case 3: 
       System.out.print("\n Key = "); 
       key = TextIO.getln(); 
       System.out.println(" containsKey(" + key + ") is " 
              + table.containsKey(key)); 
       break;   
      case 4: 
       System.out.print("\n Key = "); 
       key = TextIO.getln(); 
       table.remove(key); 
       break;   
      case 5: 
       table.dump(); 
       break; 
      case 6: 
       return; // End program by returning from main()   
      default: 
       System.out.println(" Illegal command."); 
       break; 
     } 
     System.out.println("\nHash table size is " + table.size()); 
    } 
    } 

} // end class TestHashTable 

Answer 5

// Java program to demonstrate implementation of our 
// own hash table with chaining for collision detection 
import java.util.ArrayList; 

// A node of chains 
class HashNode<K, V> 
{ 
    K key; 
    V value; 

    // Reference to next node 
    HashNode<K, V> next; 

    // Constructor 
    public HashNode(K key, V value) 
    { 
     this.key = key; 
     this.value = value; 
    } 
} 

// Class to represent entire hash table 
class Map<K, V> 
{ 
    // bucketArray is used to store array of chains 
    private ArrayList<HashNode<K, V>> bucketArray; 

    // Current capacity of array list 
    private int numBuckets; 

    // Current size of array list 
    private int size; 

    // Constructor (Initializes capacity, size and 
    // empty chains. 
    public Map() 
    { 
     bucketArray = new ArrayList<>(); 
     numBuckets = 10; 
     size = 0; 

     // Create empty chains 
     for (int i = 0; i < numBuckets; i++) 
      bucketArray.add(null); 
    } 

    public int size() { return size; } 
    public boolean isEmpty() { return size() == 0; } 

    // This implements hash function to find index 
    // for a key 
    private int getBucketIndex(K key) 
    { 
     int hashCode = key.hashCode(); 
     int index = hashCode % numBuckets; 
     return index; 
    } 

    // Method to remove a given key 
    public V remove(K key) 
    { 
     // Apply hash function to find index for given key 
     int bucketIndex = getBucketIndex(key); 

     // Get head of chain 
     HashNode<K, V> head = bucketArray.get(bucketIndex); 

     // Search for key in its chain 
     HashNode<K, V> prev = null; 
     while (head != null) 
     { 
      // If Key found 
      if (head.key.equals(key)) 
       break; 

      // Else keep moving in chain 
      prev = head; 
      head = head.next; 
     } 

     // If key was not there 
     if (head == null) 
      return null; 

     // Reduce size 
     size--; 

     // Remove key 
     if (prev != null) 
      prev.next = head.next; 
     else 
      bucketArray.set(bucketIndex, head.next); 

     return head.value; 
    } 

    // Returns value for a key 
    public V get(K key) 
    { 
     // Find head of chain for given key 
     int bucketIndex = getBucketIndex(key); 
     HashNode<K, V> head = bucketArray.get(bucketIndex); 

     // Search key in chain 
     while (head != null) 
     { 
      if (head.key.equals(key)) 
       return head.value; 
      head = head.next; 
     } 

     // If key not found 
     return null; 
    } 

    // Adds a key value pair to hash 
    public void add(K key, V value) 
    { 
     // Find head of chain for given key 
     int bucketIndex = getBucketIndex(key); 
     HashNode<K, V> head = bucketArray.get(bucketIndex); 

     // Check if key is already present 
     while (head != null) 
     { 
      if (head.key.equals(key)) 
      { 
       head.value = value; 
       return; 
      } 
      head = head.next; 
     } 

     // Insert key in chain 
     size++; 
     head = bucketArray.get(bucketIndex); 
     HashNode<K, V> newNode = new HashNode<K, V>(key, value); 
     newNode.next = head; 
     bucketArray.set(bucketIndex, newNode); 

     // If load factor goes beyond threshold, then 
     // double hash table size 
     if ((1.0*size)/numBuckets >= 0.7) 
     { 
      ArrayList<HashNode<K, V>> temp = bucketArray; 
      bucketArray = new ArrayList<>(); 
      numBuckets = 2 * numBuckets; 
      size = 0; 
      for (int i = 0; i < numBuckets; i++) 
       bucketArray.add(null); 

      for (HashNode<K, V> headNode : temp) 
      { 
       while (headNode != null) 
       { 
        add(headNode.key, headNode.value); 
        headNode = headNode.next; 
       } 
      } 
     } 
    } 

    // Driver method to test Map class 
    public static void main(String[] args) 
    { 
     Map<String, Integer>map = new Map<>(); 
     map.add("this",1); 
     map.add("coder",2); 
     map.add("this",4); 
     map.add("hi",5); 
     System.out.println(map.size()); 
     System.out.println(map.remove("this")); 
     System.out.println(map.remove("this")); 
     System.out.println(map.size()); 
     System.out.println(map.isEmpty()); 
    } 
} 

Answer 6

private ITEM[] st; private int N, M; ST(int maxN) { N = 0; M = 4; st = new ITEM[M]; } private void expand() { ITEM[] t = st; N = 0; M = M+M; st = new ITEM[M]; for (int i = 0; i < M/2; i++) if (t[i] != null) insert(t[i]); } void insert(ITEM x) { int i = hash(x.key(), M); while (st[i] != null) i = (i+1) % M; st[i] = x; if (N++ >= M/2) expand(); } 

Answer 7

/* 
     A little program to test the HashTable class. Note that I 
     start with a really small table so that I can easily test 
     the resize() method. 
    */ 

    public class TestHashTable { 

     public static void main(String[] args){ 
     HashTable table = new HashTable(2); 
     String key,value; 
     while (true) { 
      System.out.println("\nMenu:"); 
      System.out.println(" 1. test put(key,value)"); 
      System.out.println(" 2. test get(key)"); 
      System.out.println(" 3. test containsKey(key)"); 
      System.out.println(" 4. test remove(key)"); 
      System.out.println(" 5. show complete contents of hash table."); 
      System.out.println(" 6. EXIT"); 
      System.out.print("Enter your command: "); 
      switch (TextIO.getlnInt()) { 
       case 1: 
        System.out.print("\n Key = "); 
        key = TextIO.getln(); 
        System.out.print(" Value = "); 
        value = TextIO.getln(); 
        table.put(key,value); 
        break;   
       case 2: 
        System.out.print("\n Key = "); 
        key = TextIO.getln(); 
        System.out.println(" Value is " + table.get(key)); 
        break;   
       case 3: 
        System.out.print("\n Key = "); 
        key = TextIO.getln(); 
        System.out.println(" containsKey(" + key + ") is " 
               + table.containsKey(key)); 
        break;   
       case 4: 
        System.out.print("\n Key = "); 
        key = TextIO.getln(); 
        table.remove(key); 
        break;   
       case 5: 
        table.dump(); 
        break; 
       case 6: 
        return; // End program by returning from main()   
       default: 
        System.out.println(" Illegal command."); 
        break; 
      } 
      System.out.println("\nHash table size is " + table.size()); 
     } 
     } 

    } // end class TestHashTable 

Answer 8

Hashtable implements a key value pair kind of collection 
*/ 
import java.util.*; 
public class HashtableDemo { 
    static String newLine = System.getProperty("line.separator"); 
    public static void main(String[] args) { 

    System.out.println(newLine + "Hashtable in Java" + newLine); 
    System.out.println("-----------------------" + newLine); 
    System.out.println("Adding items to the Hashtable" + newLine); 
    //Creating Hashtable object 
    //dictionary can be created using HashTable object 
    //as dictionary is an abstract class 
    Hashtable ht = new Hashtable(); 

    //you add elements to Hashtable using put method 
    //put(key, value) 
    ht.put("Java", 1); 
    ht.put(".NET", 2); 
    ht.put("Javascript", 3); 
    ht.put("HTML", 4); 

    //You will see that the items will be arranged as per the hash function 
    System.out.println(newLine + "Items in the Hashtable..." + ht + newLine); 
    System.out.println("-----------------------" + newLine); 

    //looping through all the elements in hashtable 
    String str; 
    //you can retrieve all the keys in hashtable using .keys() method 
    Enumeration names = ht.keys(); 
     while(names.hasMoreElements()) { 
      //next element retrieves the next element in the dictionary 
     str = (String) names.nextElement(); 
     //.get(key) returns the value of the key stored in the hashtable 
     System.out.println(str + ": " + ht.get(str) + newLine); 
     } 
    } 
}