扩展哈希是最好的哈希方法之一，我想创建一个Java程序来进行可扩展哈希。是否有可用于此目的的API？如果没有API且可能的话，请发布算法。
我该如何在Java中实现可扩展哈希？
3
- professionalcoder2010
2
嗨Senthil，从目前为止的答案来看，似乎很难找到你所要求的代码。我和Arun一样好奇，你为什么需要更好的哈希算法？这是一个性能问题吗？ - Todd Owen
感谢您对此的关注，Todd Owen先生。当然，这是出于性能问题。 - professionalcoder2010
8个回答
3
我只是好奇，为什么你需要实现这样的算法？标准的Java Map实现对你来说表现不佳吗？如果你遇到了bucket过度加载的问题，你可能想先查看hashCode()方法，而不是选择非标准路线。另一种选择也可以是查看GNU Trove提供的一些选项。
最后 - 与Extendible类似的算法是Cuckoo哈希。以下是一些信息：
最后 - 与Extendible类似的算法是Cuckoo哈希。以下是一些信息：
http://en.wikipedia.org/wiki/Cuckoo_hashing
源代码在这里：
- Scruffers
1
Arun，谢谢你提供的链接，我只是在寻找可扩展哈希。 - professionalcoder2010
1
这个文件定义了一个HashTable类。哈希表中的键和值都是Object类型的。键不能为空。默认构造函数创建一个初始具有64个位置的表，但可以通过构造函数的参数指定不同的初始大小。如果表格超过3/4满，则会增加表格的大小。
一个测试HashTable的程序：
一个小程序用于测试HashTable类。请注意，我从一个非常小的表开始，以便可以轻松测试resize()方法。
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
- user7457036
0
前言: 我不知道什么是可扩展哈希。
根据我从这个维基上所理解的(http://en.wikipedia.org/wiki/Extendible_hashing)， 它可以使用最多两个查找来搜索，你可能想看一下Bernstein DB (sg-cDB)的Java实现。http://cr.yp.to/cdb.html
根据我从这个维基上所理解的(http://en.wikipedia.org/wiki/Extendible_hashing)， 它可以使用最多两个查找来搜索，你可能想看一下Bernstein DB (sg-cDB)的Java实现。http://cr.yp.to/cdb.html
- srini.venigalla
0
可扩展哈希的Java实现： http://en.wikibooks.org/wiki/Data_Structures/Hash_Tables#A_Java_implementation_of_extendible_hashing
如srini.venigalla所说...Bernstein的sg-cDB很好。您可以在GitHub上找到Michael Alyn Miller纯Java制作的CDB移植版本：https://github.com/malyn/sg-cdb
- ggrandes
0
// 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());
}
}
- user7457067
1
3仅包含代码的答案对社区来说并不有用。请查看[答案]。 - JimHawkins
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(); }
- user7457067
1
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
- user7457067
1
0
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);
}
}
}
- user7457067
1
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接