Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

CS 3345 > Hash Tables > Flashcards

Hash Tables Flashcards

(62 cards)

Start Studying
1
Q

What is the makeEmpty() algorithm?

A

currentSize= 0;

For(0-Array.Length()) array[i] = null;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

When do we check the load factor?

A

In the insert algorithm, after the insert is done.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are the 10 functions that implement a Separate Chaining HashTable?

A
  1. Constructor()
  2. Constructor(size)
  3. Insert()
  4. Remove()
  5. Contains()
  6. MakeEmpty()
  7. Rehash()
  8. Hash()
  9. NextPrime()
  10. IsPrime()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the probability that an object will be inserted without a collision?

A

1-(the load factor)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does HashTable(Size) do?

A

Sends size to nextPrime() and allocates an array of lists the size returned by nextPrime.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the remove algorithm?

A
  • remove(object x)
    • findPos(x);
    • if(isActive(pos)) array.[pos].isActive = false;
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What must be done after every insertion to a hashtable?

A

The size must be incremented.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What are the eleven methods of a quadratic probing table?

A
  1. makeEmpty()
  2. contains(object)
  3. insert(object)
  4. remove(object)
  5. hash()
  6. nextPrime(int)
  7. isPrime(int)
  8. rehash()
  9. findPos()
  10. isActive(int pos)
  11. allocateArray(int size)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

For an ideal hash table, what is the mean number of probes needed to insert an object, or an unsuccessful search?

A

1⁄(1-∧)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is hashing used for?

A

Hashing is used to perform insertions, deletions, and searches in constant average time.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

In Java, if an Int is overflowed what happens?

A

The int becomes a negative value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How does a hash Function work?

A

The hash function generally computes some hashcode from the objects key and then returns that hashCode mod tableSize

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

When do we check the load factor?

A

After every insertion.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the insert algorithm?

A
  • insert(object x)
    • int currentPos = findPos(x);
    • if(isActive(pos)) return;
    • Array[pos] = new HashEntry(x, true);
    • if(++currentSize > array.length/2) rehash();
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is the contains algorithm?

A
  • Contains(object x)
    • int pos = findPos(x);
    • return isActive(pos);
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the average times for search and delete on a Hash Table that uses separate chaining?

A

1 + loadfactor/2

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is the load factor?

A

The load factor is the ratio of Nodes to tableSize.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Use horner’s rule on the following code:
for(int i = 0; i < key.length; i++)
hashcode + = key[i]*pow(26, i);

A

hashcode = 26*hashcode + key[i];

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is rehashing?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What form of prime allows the entire table to be probed in a quadratic hash table?

A

A prime of form 4k + 3

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

what is generally the load factor for tables that do not use separate chaining?

A

it should be below .5

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the probability of needing i probes to insert an object?

A

∧(i-1)(1 - ∧)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What collision resolution implementation gives the closest results to ideal run time?

A

Double Hashing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is primary clustering?

A

Primary clustering is a behavior caused by linear probing that causes blocks of occupied cells to start forming due to linear collision resolution.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
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.
26
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.
27
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.
28
What is a key?
The key is some data field of the object on which a search is performed.
29
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();
30
What is the fundamental data structure for a hashtable?
An array of some fixed size.
31
When do we call Rehash() for separate chaining hash tables?
When the load factor is equal to 1.
32
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.
33
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.
34
What is quadratic probing?
A collision resolution method that eliminates the primary clustering problem using a quadratic collision function.
35
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.
36
What is the runtime of rehashing?
O(N).
37
What is the allocate array algorithm?
* allocateArray(arraySize) * array = new hashEntry[nextPrime(size)];
38
What is the average length of a list in a Separate chaining hash table?
The load factor.
39
What is the general probing function?
(hash(x) + f(i)) mod TableSize
40
What are two collision resolutions used in Hash Tables?
Separate chaining and open-addressing.
41
What is the range of numbers that a key can be mapped to?
Keys can be mapped from 0 - (TableSize -1)
42
What must be done after every deletion from a hash table?
The size must be decremented.
43
What are the two constructor algorithms for a HashTable?
HashTable() { this(Default\_Size); } HashTable(int size) { allocateArray(size); makeEmpty(); }
44
What is the fundamental data structure for a hashtable?
An array of some fixed size.
45
What is f(i) for linear probing?
f(i) = i;
46
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.
47
What does ideal hash table mean?
No deletions occur, and the probing scheme does not cause clustering.
48
What is the isActive algorithm?
* isActive(int Pos) * return array[pos] !null && array[pos].isActive;
49
What is the mean time for an insertion or an unsuccessful search in a hash table that uses linear probing?
½(1 + 1/(1-∧)2
50
Each entry in the array of hashEntries must be what?
Null Not Null, and IsActive is ture. Not Null, and IsActive is False.
51
What are the three possible rehash conditions for a quadratic probing table?
1. rehash as soon as the table is half full. 2. rehash at a certain load factor. 3. rehash when insertion fails.
52
For an idea hash table, what is the mean number of probes needed in a successful search?
1⁄∧ ln 1⁄1-∧
53
What is the mean time for a successful search in a linear probing hash table?
½(1+1/(1-∧)
54
What is a collision?
A collision is when two keys hash to the same value.
55
A probing table must use what for deletion?
lazy deletion
56
What are the four data elements to a quadratic probing class?
Default table Size Current Size Array of Hash Entries nested hash entry class
57
What is a the f(i) function for double hashing?
return i\*hash2(x);
58
What is a hash function?
A hash function maps each key an object to some number in the table.
59
In an open hashing table, search wills stop at what?
At a cell that is a null link.
60
In an open hashing table, insertion findPos stops at what?
Insertion will stop at a cell that is not active.
61
The constructors in a HashTable must do what?
Initialize the array of linked lists or Nodes.
62
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.

CS 3345 (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions