Hash/ HashMap

✅ Hash

key ➕ value

for the efficient management of data,
mapping data of arbitary length to fixed-length
generate fixed-size output of an input of variable size
using hash functions

💡 Components of hashing

• key: what to hash?
• hash function: input key ➡️ return index(hash index) of an element in an array

• hash array: map key to value

• 👍🏻 search data with index fast: time complexity: O(1)
• 👍🏻 However, in case of collison, need to search chaining list, thus time complexity: O(N)

⚠️ Collision

when two keys produce the same value

💊 Ways to solve collision

• chanining: add node as linked list 👎🏻 memory
• open addressing: 해시함수로 얻어진 주소가 아닌 다른 주소에 저장 허용
• 선형 탐사
• 제곱 탐사
• linked list

✔️ how to search data in hash when collision occurs

data search in collision can be done with

• linked list(save value of key)
• tree

👍🏻 Advantages of hashing

• key-value
• fast data retrieval(search): time complexity O(1)
• efficiency for insertion, deletion
• memory usage reduction
• scalability
• security, encryption

✅ HashMap

Picture of hash map https://soheeparklee.github.io/posts/JAVA_set_map/

• HashTable ➕ Map
• save key-value on hash table
• hash code, to function as object identifier
• 👍🏻 search
• ⚠️ when collision occurs, use linked list

Hash table 🆚 BST

• 공통점: used in data search

• Hash table

  • save data based on key-value
  • search time complexity O(1)
  • 👎🏻 waste memory
  • 👎🏻 search slow when collision

• Binary Search Table

  • search done by comparing node value
  • search time complexity in worst scenario O(N)

Hash 🆚 Encryption 🆚 Encoding

https://soheeparklee.github.io/posts/Jasypt-Encryption/