Are u a bored programmer? if so, Talk to me about java hash tables!
- Thread starter SnoopCat
- Start date
and I have no idea about them.. so if anyone wants to talk about them.. you have another listener 
what should i say? they are easy to use. pretty useful, they are in the java.util.hashtable
i need questions
i need questions
public class Hashtable
extends Dictionary
implements Map, Cloneable, Serializable
This class implements a hashtable, which maps keys to values. Any non-null object can be used as a key or as a value.
To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.
An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case a "hash collision", a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hashtable exceeds the product of the load factor and the current capacity, the capacity is increased by calling the rehash method.
Generally, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the time cost to look up an entry (which is reflected in most Hashtable operations, including get and put).
The initial capacity controls a tradeoff between wasted space and the need for rehash operations, which are time-consuming. No rehash operations will ever occur if the initial capacity is greater than the maximum number of entries the Hashtable will contain divided by its load factor. However, setting the initial capacity too high can waste space.
If many entries are to be made into a Hashtable, creating it with a sufficiently large capacity may allow the entries to be inserted more efficiently than letting it perform automatic rehashing as needed to grow the table.
This example creates a hashtable of numbers. It uses the names of the numbers as keys:
Hashtable numbers = new Hashtable();
numbers.put("one", new Integer(1));
numbers.put("two", new Integer(2));
numbers.put("three", new Integer(3));
To retrieve a number, use the following code:
Integer n = (Integer)numbers.get("two"
if (n != null) {
System.out.println("two = " + n);
}
As of JDK1.2, this class has been retrofitted to implement Map, so that it becomes a part of Java's collection framework. Unlike the new collection implementations, Hashtable is synchronized.
The Iterators returned by the iterator and listIterator methods of the Collections returned by all of Hashtable's "collection view methods" are fail-fast: if the Hashtable is structurally modified at any time after the Iterator is created, in any way except through the Iterator's own remove or add methods, the Iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the Iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. The Enumerations returned by Hashtable's keys and values methods are not fail-fast.
extends Dictionary
implements Map, Cloneable, Serializable
This class implements a hashtable, which maps keys to values. Any non-null object can be used as a key or as a value.
To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.
An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. Note that the hash table is open: in the case a "hash collision", a single bucket stores multiple entries, which must be searched sequentially. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hashtable exceeds the product of the load factor and the current capacity, the capacity is increased by calling the rehash method.
Generally, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the time cost to look up an entry (which is reflected in most Hashtable operations, including get and put).
The initial capacity controls a tradeoff between wasted space and the need for rehash operations, which are time-consuming. No rehash operations will ever occur if the initial capacity is greater than the maximum number of entries the Hashtable will contain divided by its load factor. However, setting the initial capacity too high can waste space.
If many entries are to be made into a Hashtable, creating it with a sufficiently large capacity may allow the entries to be inserted more efficiently than letting it perform automatic rehashing as needed to grow the table.
This example creates a hashtable of numbers. It uses the names of the numbers as keys:
Hashtable numbers = new Hashtable();
numbers.put("one", new Integer(1));
numbers.put("two", new Integer(2));
numbers.put("three", new Integer(3));
To retrieve a number, use the following code:
Integer n = (Integer)numbers.get("two"
;if (n != null) {
System.out.println("two = " + n);
}
As of JDK1.2, this class has been retrofitted to implement Map, so that it becomes a part of Java's collection framework. Unlike the new collection implementations, Hashtable is synchronized.
The Iterators returned by the iterator and listIterator methods of the Collections returned by all of Hashtable's "collection view methods" are fail-fast: if the Hashtable is structurally modified at any time after the Iterator is created, in any way except through the Iterator's own remove or add methods, the Iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the Iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. The Enumerations returned by Hashtable's keys and values methods are not fail-fast.
I have a quiz tomorrow morning on them, and wrote a program tonight implementing them...funny coincidence
Um...if it's a far ratio, you have a lot of wasted space/memory allocation, but if it's too close you'll wind up with a lot of collisions...
/uhhh, me gets book
/uhhh, me gets book
well...it can use separate chaining to build lists of the elements that hashed to the same value...or if it's linear or quadratic it will go through the table looking linearly/quadratically (that a word? ) for an empty space until it runs out (after wrap around(s))...then you can rehash
I gotta go to sleeeeeeep, thanks for the quiz
) for an empty space until it runs out (after wrap around(s))...then you can rehash I gotta go to sleeeeeeep, thanks for the quiz
virtuamike
Diamond Member
- Oct 13, 2000
- 7,845
- 13
- 81
Separate chaining will build a list for values that hash to the same value. Depending on what your expected input is, this could be a good way or a very bad way to implement your hash. If you get a lot of collisions and long lists, then your time for insertion goes from O(1) to O(N), and that sucks. All depends on how long you expect the list to get and how big your initial table is. For example, bad idea to set table size to 10 for 1000 expected entries and a hash function of hash(X) = X%TableSize.
Linear and quadratic both add functions to resolve collisions. In other words, hash(X)= X%TableSize + f(i), with i incrementing from 0. f(i) is i for linear and i*i for quadratic. Meaning if there's a collision in linear, you just go to the next available opening. With quadratic you try 1 over, then 4 over, then 9 over, and so on. You need a load average of 0.5 for quadratic to guarantee a successful insertion, plus you need to make sure the table size is prime. When you need to rehash, double the table size and round up to the next prime.
Linear and quadratic both add functions to resolve collisions. In other words, hash(X)= X%TableSize + f(i), with i incrementing from 0. f(i) is i for linear and i*i for quadratic. Meaning if there's a collision in linear, you just go to the next available opening. With quadratic you try 1 over, then 4 over, then 9 over, and so on. You need a load average of 0.5 for quadratic to guarantee a successful insertion, plus you need to make sure the table size is prime. When you need to rehash, double the table size and round up to the next prime.
TRENDING THREADS
-
Discussion Zen 5 Speculation (EPYC Turin and Strix Point/Granite Ridge - Ryzen 9000)- Started by DisEnchantment
- Replies: 25K
-
Discussion Intel Meteor, Arrow, Lunar & Panther Lakes + WCL Discussion Threads
- Started by Tigerick
- Replies: 23K
-
Discussion Intel current and future Lakes & Rapids thread- Started by TheF34RChannel
- Replies: 23K
-
-
Facebook
Twitter