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

42 views1 pages
School
Course
Professor
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)
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
Unlock document

This preview shows half of the first page of the document.
Unlock all 1 pages and 3 million more documents.

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)

Get access

\$8 USD/m\$10 USD/m
Billed \$96 USD annually
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class