laishuacode

拆不散D大熊小熊

8逻辑层面！数学层面：is概念上的：所有 有get put 接口的，存储的是一堆 a collection of ..

hash table & string
a collection of key-value pairs
associate one data type associate to another data type
ex: use ID find user info => has table
1. get（key）=>value
Array != quick同上  logN for search   O(N）insert/delete one and then
move forw
2. put(key, value) key value传成一个pair 插入到 hash table里（key重复的话 会替换掉新value）

实现：hash map hash set 等类 ）ptyhon dictionary语言里具体的类名字
实例实例！ hash is a general data structure
Hashtable HashMap and HashSet(有key无value） are its implementation classes in Java/
实现多样 只需一个接口get put就这两个接口就这么简单；（stack queue）
他们是逻辑层面的数据结构


example:  a small phone book as a hash table
hashtable<string, string>
key = name:string  value = phone n : string
keys          hash function      buckets
                                       oo  nulll
john smith                        o1  531- ''
lisa smith                          o2
sand d
..............................          15
hash function 's input is keys like name ; return index(int) 0 =15
  这个例子里面吃掉一个name吐出一个index 2（直接读取2里面的电话号码）
插入也是一样 吃（用hash function转化一下）人名吐出（hash function的返回值）index1 然后加上电话号码


上面是理想化的，but 现实有 hash clustering
separate chaining


array of bucket（ combine with； linkedlist（这就是为啥要放 name/key进去因为可能两个人用的都是bucket 152 一样才返回value））


这就是 worst case O(n） 查找插入都是O（n）！！嘻嘻


超级简单面试题：

Q1：For a composition of words try to find the top k frequent words in the composition
记住面试clarify！！！！！！！！
文字 string 类型？  
a list of words each word is a string 【‘a’，‘’】
大小写
k 《= 10000
propose  my method

Hashtable<key = word( of string), value =frequent(of Integer）>
Step 1: for each word in the list
       if hashtable.get(word) == null
          hashtable.put(word, 1)
       else:
          int freq = hashtable.get(word);
          hashtable.put(word, freq +1);

// hashtable.put(word, hashtable.getOrDefault(word, 0)+1);

拆不散D大熊小熊

https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
system design！！