Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CS 3345 > Hash Tables > Flashcards

Hash Tables Flashcards

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
Q

What does the constructor of a quadratic probing table do?

A

Allocates an array of the default size, or a size given as the argument, and then sets every entry to null.

26
Q

What is TableSize?

A

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
Q

When are we guaranteed to find a cell to insert a node in a hash table that implements quadratic probin?

A

when the load factor is .5, and the table size is prime.

28
Q

What is a key?

A

The key is some data field of the object on which a search is performed.

29
Q

What is the findPos algorithm?

A
  • 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
Q

What is the fundamental data structure for a hashtable?

A

An array of some fixed size.

31
Q

When do we call Rehash() for separate chaining hash tables?

A

When the load factor is equal to 1.

32
Q

What is separate chaining?

A

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
Q

Why should we avoid using the built in List implementation when space is tight?

A

Because they are doubly linked lists, and use twice as many references.

34
Q

What is quadratic probing?

A

A collision resolution method that eliminates the primary clustering problem using a quadratic collision function.

35
Q

What is a second hash function that will not evaluate to zero?

A

return R - (hash(x) mod R), where R is a prime smaller than the table size.

36
Q

What is the runtime of rehashing?

A

O(N).

37
Q

What is the allocate array algorithm?

A
  • allocateArray(arraySize)
    • array = new hashEntry[nextPrime(size)];
38
Q

What is the average length of a list in a Separate chaining hash table?

A

The load factor.

39
Q

What is the general probing function?

A

(hash(x) + f(i)) mod TableSize

40
Q

What are two collision resolutions used in Hash Tables?

A

Separate chaining and open-addressing.

41
Q

What is the range of numbers that a key can be mapped to?

A

Keys can be mapped from 0 - (TableSize -1)

42
Q

What must be done after every deletion from a hash table?

A

The size must be decremented.

43
Q

What are the two constructor algorithms for a HashTable?

A

HashTable()

{

this(Default_Size);

}

HashTable(int size)

{

allocateArray(size);

makeEmpty();

}

44
Q

What is the fundamental data structure for a hashtable?

A

An array of some fixed size.

45
Q

What is f(i) for linear probing?

A

f(i) = i;

46
Q

What kind of operations are not generally supported with hash tables?

A

Tree operations that require any ordering information like findMin, or findMax, or printing a table in sorted order.

47
Q

What does ideal hash table mean?

A

No deletions occur, and the probing scheme does not cause clustering.

48
Q

What is the isActive algorithm?

A
  • isActive(int Pos)
    • return array[pos] !null && array[pos].isActive;
49
Q

What is the mean time for an insertion or an unsuccessful search in a hash table that uses linear probing?

A

½(1 + 1/(1-∧)2

50
Q

Each entry in the array of hashEntries must be what?

A

Null

Not Null, and IsActive is ture.

Not Null, and IsActive is False.

51
Q

What are the three possible rehash conditions for a quadratic probing table?

A
  1. rehash as soon as the table is half full.
  2. rehash at a certain load factor.
  3. rehash when insertion fails.
52
Q

For an idea hash table, what is the mean number of probes needed in a successful search?

A

1⁄∧ ln 1⁄1-∧

53
Q

What is the mean time for a successful search in a linear probing hash table?

A

½(1+1/(1-∧)

54
Q

What is a collision?

A

A collision is when two keys hash to the same value.

55
Q

A probing table must use what for deletion?

A

lazy deletion

56
Q

What are the four data elements to a quadratic probing class?

A

Default table Size

Current Size

Array of Hash Entries

nested hash entry class

57
Q

What is a the f(i) function for double hashing?

A

return i*hash2(x);

58
Q

What is a hash function?

A

A hash function maps each key an object to some number in the table.

59
Q

In an open hashing table, search wills stop at what?

A

At a cell that is a null link.

60
Q

In an open hashing table, insertion findPos stops at what?

A

Insertion will stop at a cell that is not active.

61
Q

The constructors in a HashTable must do what?

A

Initialize the array of linked lists or Nodes.

62
Q

When implementing double hashing, what must the hash function never evaluate to?

A

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.
© 2024 Bold Learning Solutions. Terms and Conditions