HashTable

Question 1

What is a hashcode?

Answer 1

A hashcode is used to create a key for an item.

The hashcode may be the same as the value of the item or may involve the use of some elaborate formula in hopes of creating a unique key.

Question 2

What is the output of the code?

Character c = new Character('a');
out.println(c.hashCode());
c = new Character('0')
;out.println(c.hashCode());
c = new Character('A');
out.println(c.hashCode());

Answer 2

97
48
65

Question 3

What is a hash table?

Answer 3

A hash table stores values based on the hash code of each value.

Most hash tables are built using an ARRAY of LINKED LISTS.

HashSet and HashMap were both created around hash tables.

Yet, Hash Tables are similar to Maps.

Question 4

What’s an example of a hash table?

Answer 4

Object[] hashTable = new Object[10];

Character c = new Character(‘l’);
hashTable[c.hashCode()%10] = c;

Question 5

What are Collisions

Answer 5

Anytime you use a hash formula to generate index positions, you could end up with the same index position for several values.

Question 6

How are collisions handled?

Answer 6

Collisions are handled by putting all the values with the same hash code in a list and storing the list at the index position the matches the hash code.

Question 7

What is Bucket Hashing/Chaining?

Answer 7

Using a bucket or a chan is a common way to describe putting all of the values with the same hash code in one list.

Basically to handle collisions.

The larger the array the less likely you are to have collisions.

Question 8

Could you also use ListNode as LinkedLists in HashTables?

Answer 8

Yes, you could as they work well to chain items together.

ex) ListNode[] table = new ListNode[100];