HashMap Implementation

Date: April 10, 2023

Topic: Hash Table

Recall

definition

Q1 找到出现频率第k高的词

Q2 在unsorted array找one missing number

O(n) time

Find the common numbers between two sorted arrays a[M], b[N]

String

2类常考问题

Notes

• set: all elements are unique

• Hash table is a general data structure

  • HashMap and HashSet are its implementation classes in Java.
    • HashSet<key>
    • HashMap<key, value> pairs, not allow duplicate keys

• Implementation

  • hash collision
    • chaining
    • open address (probe + rehash)

• 增删查改都是O(1)的时间复杂度

• HashSet返回boolean，表示是否add成功

• HashMap，put一个不存在的key=add， put一个存在的key = update

• step1:先统计每个单词出现了多少次：遍历input list，对于每个单词统计次数 O(n) time in average

• 核心数据结构：minHeap， online算法

• step2: 再top k online

  • TC：klogk + (n-k) * logk = klogk + nlogk - klogk = nlogk
  • 用heapify： k + (n-k)logk = nlogk

• step3: 需要结果按照freq降序排列，倒着加结果

• 最后return的结果与minHeap的size有关系

• TC：nlogk

• 用maxHeap做这题是offline，且时间复杂度有区别

• Solution1: Hash table(hash set):

  • step1: insert all numbers in the input array to a hash set
  • step2: for each number from 1 to n, find whether it’s in the hash table
  • TC: O(n), SC: O(n)

• Solution2: Array： boolean occurred[n+1]

  • step1: for each number(x) in the input array: occurred[x] = true;
  • step2: traverse array, if occurred[i] == false, return i;

• Solution3: mathematical way

  • 把完整的[i,n]相加减去该array，得到的就是missing number

• Solution4: bit operation; xor

  

  

  （1 xor 2 xor 3 …xor n) xor (a[0] xor a[1] xor … xor a[n-1]) = the missing number!

  • TC: O(n) SC: O(1), bit operation: O(1)

• Solution1: TC: O(m+n), SC: O(min(m,n))

  • step1:把长度较短的array放到hashset，O(min(m,n))
  • step2: iterate over the other array to find common elements, O(max(m,n))

• Solution2: 谁小移谁 TC：O(m+n), SC: O(1)

• Solution 3: Binary Search TC: O(mlogn) SC: O(1)

• which better:

<aside> 📌 SUMMARY: 1. 不要盲目使用API，尤其是你在不知道复杂度的时候. 2. in Java, string is immutable!

</aside>

Date: April 12, 2023

Topic: Practice 11 Map/ Set/ Hash

<aside> 📌 SUMMARY:

</aside>

Date: April 14, 2023

Topic: Practice 12 HashMap Implementation

<aside> 📌 SUMMARY:

</aside>