All geek questions in one place

How can I implement extensible hashing in java?

extensible hashing is one of the best hashing methods, I want to create a program in java for advanced hashing. is there any api for this? I do not get a clear algorithm for this myself, so if there is no api, .if a possible post algoirhtm

+3
source share
8 answers

I'm just wondering why you need such an algorithm? Are standard Java Map implementations not for you? If you encounter the problem of loading the buckets too much, you can take a look at the hashCode () method before choosing non-standard routes. An alternative could also be to view some of the options provided by GNU Trove.

, Extendible . :

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

:

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

+3

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:
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
+1
// 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());
    }
}
0
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();  }
0
/*
      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
0
source 
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);
      }
  }
}
0
source

Source: https://habr.com/ru/post/1729777/

More articles:


All Articles