# CS 0445 Lecture Notes - Lecture 30: Linear Probing, Prime Number

HASH TABLES:

- is just an array

- typically prime number of elements

Hash Code via .hashcode() - > Address -> Store somehwhere in hashtable

How to fit hc into ht

- Address is dependent on the number of elements in the array

Ex:

hashcodes = 43, 41, 91, 22, 11, 24

remaineder by % 11 for even spread into table

array locations = 10, 8, 3, 0, 0, 2

- hashtable look up is a O(1) operation

- can only hold unique items

- thats why is good for sets

Note: Collision at values of hashcode 22 and 11

Solve via linear probing (adding to next available space)

which increases load factor

An instance of HashMap 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. The load factor is a measure of how full the hash table is

allowed to get before its capacity is automatically increased

- load factor of 0.5 makes operations O(n)

- ADD () is usually big of O(n) but when rehash we have to resize the array and

re-address it so it becomes O(n) temporarily

- to avoid this we initialize hash table as (*2 + 1) of the number of elements

Note:

Another collision checking stratergy: SEPERATE CHAINING

Store in Array of Nodes <T> [(11)-->(22)]

Stores last collision as the first node in the array block, then point the older

collisiona as its next

Manages load factor better (goes to 0.7)

find more resources at oneclass.com

find more resources at oneclass.com

## Document Summary

Hash code via . hashcode() - > address -> store somehwhere in hashtable. Address is dependent on the number of elements in the array. Ex: hashcodes remaineder by % 11 for even spread into table array locations = 10, 8, 3, 0, 0, 2. Hashtable look up is a o(1) operation. Note: collision at values of hashcode 22 and 11. Solve via linear probing (adding to next available space) which increases load factor. An instance of hashmap 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. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. Load factor of 0. 5 makes operations o(n)