6
यहाँ जावा प्रोग्रामिंग करने के लिए परिचय से एक उदाहरण (लिआंग) है:हैशसेट में समान रूप से वितरित हैशिंग सुनिश्चित करें, यह कैसे काम करता है?
/** Ensure the hashing is evenly distributed */
private static int supplementalHash(int h) {
h ^= (h >>> 20)^(h >>> 12);
return h^(h >>> 7)^(h >>> 4);
}
आपरेशन सभी स्पष्ट हैं, लेकिन वे इस प्रकार यह कैसे सुनिश्चित करते हैं:
import java.util.LinkedList;
public class MyHashSet<E> implements MySet<E> {
// Define the default hash table size. Must be a power of 2
private static int DEFAULT_INITIAL_CAPACITY = 16;
// Define the maximum hash table size. 1 << 30 is same as 2^30
private static int MAXIMUM_CAPACITY = 1 << 30;
// Current hash table capacity. Capacity is a power of 2
private int capacity;
// Define default load factor
private static float DEFAULT_MAX_LOAD_FACTOR = 0.75f;
// Specify a load factor threshold used in the hash table
private float loadFactorThreshold;
// The number of entries in the set
private int size = 0;
// Hash table is an array with each cell that is a linked list
private LinkedList<E>[] table;
/** Construct a set with the default capacity and load factor */
public MyHashSet() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a set with the specified initial capacity and
* default load factor */
public MyHashSet(int initialCapacity) {
this(initialCapacity, DEFAULT_MAX_LOAD_FACTOR);
}
/** Construct a set with the specified initial capacity
* and load factor */
public MyHashSet(int initialCapacity, float loadFactorThreshold) {
if (initialCapacity > MAXIMUM_CAPACITY)
this.capacity = MAXIMUM_CAPACITY;
else
this.capacity = trimToPowerOf2(initialCapacity);
this.loadFactorThreshold = loadFactorThreshold;
table = new LinkedList[capacity];
}
/** Remove all elements from this set */
public void clear() {
size = 0;
removeElements();
}
/** Return true if the element is in the set */
public boolean contains(E e) {
int bucketIndex = hash(e.hashCode());
if (table[bucketIndex] != null) {
LinkedList<E> bucket = table[bucketIndex];
for (E element: bucket)
if (element.equals(e))
return true;
}
return false;
}
/** Add an element to the set */
public boolean add(E e) {
if (contains(e))
return false;
if (size > capacity * loadFactorThreshold) {
if (capacity == MAXIMUM_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int bucketIndex = hash(e.hashCode());
// Create a linked list for the bucket if it is not created
if (table[bucketIndex] == null) {
table[bucketIndex] = new LinkedList<E>();
}
// Add e to hashTable[index]
table[bucketIndex].add(e);
size++; // Increase size
return true;
}
/** Remove the element from the set */
public boolean remove(E e) {
if (!contains(e))
return false;
int bucketIndex = hash(e.hashCode());
// Create a linked list for the bucket if it is not created
if (table[bucketIndex] != null) {
LinkedList<E> bucket = table[bucketIndex];
for (E element: bucket)
if (e.equals(element)) {
bucket.remove(element);
break;
}
}
size--; // Decrease size
return true;
}
/** Return true if the set contains no elements */
public boolean isEmpty() {
return size == 0;
}
/** Return the number of elements in the set */
public int size() {
return size;
}
/** Return an iterator for the elements in this set */
public java.util.Iterator<E> iterator() {
return new MyHashSetIterator(this);
}
/** Inner class for iterator */
private class MyHashSetIterator implements java.util.Iterator<E> {
// Store the elements in a list
private java.util.ArrayList<E> list;
private int current = 0; // Point to the current element in list
MyHashSet<E> set;
/** Create a list from the set */
public MyHashSetIterator(MyHashSet<E> set) {
this.set = set;
list = setToList();
}
/** Next element for traversing? */
public boolean hasNext() {
if (current < list.size())
return true;
return false;
}
/** Get the current element and move cursor to the next */
public E next() {
return list.get(current++);
}
/** Remove the current element and refresh the list */
public void remove() {
// Delete the current element from the hash set
set.remove(list.get(current));
list.remove(current); // Remove the current element from the list
}
}
/** Hash function */
private int hash(int hashCode) {
return supplementalHash(hashCode) & (capacity - 1);
}
/** Ensure the hashing is evenly distributed */
private static int supplementalHash(int h) {
h ^= (h >>> 20)^(h >>> 12);
return h^(h >>> 7)^(h >>> 4);
}
/** Return a power of 2 for initialCapacity */
private int trimToPowerOf2(int initialCapacity) {
int capacity = 1;
while (capacity < initialCapacity) {
capacity <<= 1;
}
return capacity;
}
/** Remove all e from each bucket */
private void removeElements() {
for (int i = 0; i < capacity; i++) {
if (table[i] != null) {
table[i].clear();
}
}
}
/** Rehash the set */
private void rehash() {
java.util.ArrayList<E> list = setToList(); // Copy to a list
capacity <<= 1; // Double capacity
table = new LinkedList[capacity]; // Create a new hash table
size = 0;
for (E element: list) {
add(element); // Add from the old table to the new table
}
}
/** Copy elements in the hash set to an array list */
private java.util.ArrayList<E> setToList() {
java.util.ArrayList<E> list = new java.util.ArrayList<E>();
for (int i = 0; i < capacity; i++) {
if (table[i] != null) {
for (E e: table[i]) {
list.add(e);
}
}
}
return list;
}
/** Return a string representation for this set */
public String toString() {
java.util.ArrayList<E> list = setToList();
StringBuilder builder = new StringBuilder("[");
// Add the elements except the last one to the string builder
for (int i = 0; i < list.size() - 1; i++) {
builder.append(list.get(i) + ", ");
}
// Add the last element in the list to the string builder
if (list.size() == 0)
builder.append("]");
else
builder.append(list.get(list.size() - 1) + "]");
return builder.toString();
}
}
मैं काफी इस हिस्से का पालन नहीं करते समान रूप से वितरित हैशिंग?
इस कोड के बारे में एक और सवाल, इस हिस्से में:
/** Add an element to the set */
public boolean add(E e) {
if (contains(e))
return false;
if (size > capacity * loadFactorThreshold) {
if (capacity == MAXIMUM_CAPACITY)
throw new RuntimeException("Exceeding maximum capacity");
rehash();
}
int bucketIndex = hash(e.hashCode());
// Create a linked list for the bucket if it is not created
if (table[bucketIndex] == null) {
table[bucketIndex] = new LinkedList<E>();
}
// Add e to hashTable[index]
table[bucketIndex].add(e);
size++; // Increase size
return true;
}
क्यों size++ के बाद आकार की जाँच और rehashing ब्लॉक नहीं डाल?
इसी प्रकार दो बार तत्व है जो एक आकार बदलने से चलाता जोड़ने का मतलब होगा, लेकिन वास्तव में बहुत अलग सवाल। – qed
आपने पूछा "ऑपरेशन सभी स्पष्ट हैं, लेकिन वे इस प्रकार समान रूप से वितरित हैशिंग कैसे सुनिश्चित करते हैं?" - जवाब में समझाया गया है। यदि इसका पर्याप्त उत्तर नहीं दिया गया है तो यह आपके प्रश्न को थोड़ा संकीर्ण करने में मददगार हो सकता है। –
कोई निर्धारिती हैश फ़ंक्शन स्वयं ही बाल्टी पर "वितरण" सुनिश्चित नहीं कर सकता है, इसलिए कार्यान्वयन टिप्पणी गलत है (कड़ाई से बोल रही है) गलत है। इस तरह से हैश मान को पोस्ट-प्रोसेसिंग के लिए प्रेरणा को जुड़े प्रश्न में समझाया गया है (बस बोलते हुए, यह किसी विशेष प्रकार के हैश फ़ंक्शन की कमियों के लिए क्षतिपूर्ति करता है) – meriton