查看: 1718|回复: 1


发表于 2020-4-12 07:44:15 | 显示全部楼层 |阅读模式
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
文字 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)
          int freq = hashtable.get(word);
          hashtable.put(word, freq +1);

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

 楼主| 发表于 2020-10-15 02:58:22 | 显示全部楼层
system design!!
您需要登录后才可以回帖 登录 | 立即注册

Mark一下! 看一下! 顶楼主! 感谢分享! 快速回复:

所属分类: B-School生涯


正在浏览此版块的会员 ()

手机版|ChaseDream京公网安备11010202008513号 京ICP证101109号 京ICP备12012021号

GMT+8, 2021-3-6 15:20 , Processed in 0.190105 second(s), 9 queries , Memcache On.

ChaseDream 论坛

© 2003-2021 All Rights Reserved.