Hash Tables Flashcards
What is the makeEmpty() algorithm?
currentSize= 0;
For(0-Array.Length()) array[i] = null;
When do we check the load factor?
In the insert algorithm, after the insert is done.
What are the 10 functions that implement a Separate Chaining HashTable?
- Constructor()
- Constructor(size)
- Insert()
- Remove()
- Contains()
- MakeEmpty()
- Rehash()
- Hash()
- NextPrime()
- IsPrime()
What is the probability that an object will be inserted without a collision?
1-(the load factor)
What does HashTable(Size) do?
Sends size to nextPrime() and allocates an array of lists the size returned by nextPrime.
What is the remove algorithm?
- remove(object x)
- findPos(x);
- if(isActive(pos)) array.[pos].isActive = false;
What must be done after every insertion to a hashtable?
The size must be incremented.
What are the eleven methods of a quadratic probing table?
- makeEmpty()
- contains(object)
- insert(object)
- remove(object)
- hash()
- nextPrime(int)
- isPrime(int)
- rehash()
- findPos()
- isActive(int pos)
- allocateArray(int size)
For an ideal hash table, what is the mean number of probes needed to insert an object, or an unsuccessful search?
1⁄(1-∧)
What is hashing used for?
Hashing is used to perform insertions, deletions, and searches in constant average time.
In Java, if an Int is overflowed what happens?
The int becomes a negative value.
How does a hash Function work?
The hash function generally computes some hashcode from the objects key and then returns that hashCode mod tableSize
When do we check the load factor?
After every insertion.
What is the insert algorithm?
- insert(object x)
- int currentPos = findPos(x);
- if(isActive(pos)) return;
- Array[pos] = new HashEntry(x, true);
- if(++currentSize > array.length/2) rehash();
What is the contains algorithm?
- Contains(object x)
- int pos = findPos(x);
- return isActive(pos);
What are the average times for search and delete on a Hash Table that uses separate chaining?
1 + loadfactor/2
What is the load factor?
The load factor is the ratio of Nodes to tableSize.
Use horner’s rule on the following code:
for(int i = 0; i < key.length; i++)
hashcode + = key[i]*pow(26, i);
hashcode = 26*hashcode + key[i];
What is rehashing?
Building another table that is a prime more than twice as large as the last table size, then rehashing every element in the old table to a position in the new table.
What form of prime allows the entire table to be probed in a quadratic hash table?
A prime of form 4k + 3
what is generally the load factor for tables that do not use separate chaining?
it should be below .5
What is the probability of needing i probes to insert an object?
∧(i-1)(1 - ∧)
What collision resolution implementation gives the closest results to ideal run time?
Double Hashing
What is primary clustering?
Primary clustering is a behavior caused by linear probing that causes blocks of occupied cells to start forming due to linear collision resolution.
What does the constructor of a quadratic probing table do?
Allocates an array of the default size, or a size given as the argument, and then sets every entry to null.
What is TableSize?
TableSize is a data element built into the hash table data structure itself, it is the overall size of the array, but not how many objects are in it, and it is always a prime.
When are we guaranteed to find a cell to insert a node in a hash table that implements quadratic probin?
when the load factor is .5, and the table size is prime.
What is a key?
The key is some data field of the object on which a search is performed.
What is the findPos algorithm?
- FIndPos(Object x)
- int pos = hash(x)
- int offset = 1;
- While(array[pos] ≠ null && !array[pos].object.equals(x) && array[pos].isActive());
- currentPos += offset;
- offSet += 2
- if(currentPos ≥ array.length()) currentPos - = arra.length();
What is the fundamental data structure for a hashtable?
An array of some fixed size.
When do we call Rehash() for separate chaining hash tables?
When the load factor is equal to 1.
What is separate chaining?
A hash table scheme where an array of linked lists is used and each linked list contains objects that hashed to the same value.
Why should we avoid using the built in List implementation when space is tight?
Because they are doubly linked lists, and use twice as many references.
What is quadratic probing?
A collision resolution method that eliminates the primary clustering problem using a quadratic collision function.
What is a second hash function that will not evaluate to zero?
return R - (hash(x) mod R), where R is a prime smaller than the table size.
What is the runtime of rehashing?
O(N).
What is the allocate array algorithm?
- allocateArray(arraySize)
- array = new hashEntry[nextPrime(size)];
What is the average length of a list in a Separate chaining hash table?
The load factor.
What is the general probing function?
(hash(x) + f(i)) mod TableSize
What are two collision resolutions used in Hash Tables?
Separate chaining and open-addressing.
What is the range of numbers that a key can be mapped to?
Keys can be mapped from 0 - (TableSize -1)
What must be done after every deletion from a hash table?
The size must be decremented.
What are the two constructor algorithms for a HashTable?
HashTable()
{
this(Default_Size);
}
HashTable(int size)
{
allocateArray(size);
makeEmpty();
}
What is the fundamental data structure for a hashtable?
An array of some fixed size.
What is f(i) for linear probing?
f(i) = i;
What kind of operations are not generally supported with hash tables?
Tree operations that require any ordering information like findMin, or findMax, or printing a table in sorted order.
What does ideal hash table mean?
No deletions occur, and the probing scheme does not cause clustering.
What is the isActive algorithm?
- isActive(int Pos)
- return array[pos] !null && array[pos].isActive;
What is the mean time for an insertion or an unsuccessful search in a hash table that uses linear probing?
½(1 + 1/(1-∧)2
Each entry in the array of hashEntries must be what?
Null
Not Null, and IsActive is ture.
Not Null, and IsActive is False.
What are the three possible rehash conditions for a quadratic probing table?
- rehash as soon as the table is half full.
- rehash at a certain load factor.
- rehash when insertion fails.
For an idea hash table, what is the mean number of probes needed in a successful search?
1⁄∧ ln 1⁄1-∧
What is the mean time for a successful search in a linear probing hash table?
½(1+1/(1-∧)
What is a collision?
A collision is when two keys hash to the same value.
A probing table must use what for deletion?
lazy deletion
What are the four data elements to a quadratic probing class?
Default table Size
Current Size
Array of Hash Entries
nested hash entry class
What is a the f(i) function for double hashing?
return i*hash2(x);
What is a hash function?
A hash function maps each key an object to some number in the table.
In an open hashing table, search wills stop at what?
At a cell that is a null link.
In an open hashing table, insertion findPos stops at what?
Insertion will stop at a cell that is not active.
The constructors in a HashTable must do what?
Initialize the array of linked lists or Nodes.
When implementing double hashing, what must the hash function never evaluate to?
It must never evaluate to zero, or else it will continue to probe the same cell.
