Data Structure (hash function,binary search tree)

这学期的 data structure 终于结束了。

感觉收获还是不小的。

总结了一下学了2样东西,最有用的就是 hash function

东西本身很简单，但是思想太独特了， 大大加快了搜索速度。

首先把 value to be inserted 转换成integer value, 用这个value % anothervalue， anothervalue is constant for all the values to be inserted, % 是求余数的意思。得到结果是几，就把这个数插在哪里。

比方说：valuetobeinserted=10

anothervalue=3

valuetobeinserted%another=10%3=1 ,把data 插到table的第一个slot

但是这样有个问题20%3也等于1，怎么办呢？我们在找一个数：anothervalue2

value%anothervalue2=step, 如果第一个collision了，就把从发生冲突的位置开始，跳step

比方说：6%10=6；16%10=6；there will be collision, anothervalue2=3;假设6已经在六号位。16%3=1；16将被插入5号位，如果5号位也有data,在检查4号位,以此类推

这种方式叫做 double hashing，因为有两个 hash function

还有两种解决冲突的方法，叫做brent hashing 和binary tree hashing.

第二个就是binary search tree, 这个东西很简单，每个数据有一个 priority

比方说：有一个数据在tree 顶端（只有一个数据）他的priority是10，又有数据要进来，和这个数据比较priority，如果比他大插到the first data 右边（root->right=data），如果比他小,插到他左边(root->left=data),他们subtree也都是 binary search tree

但是这样带来一个问题，就是可能插入的所有的data to be inserted 都比那个数大，那么他的右边就会越来越长，为了保持平衡，有人想出了AVL ,tree和left leaning red black tree, 这两种 binary search tree，左右两边基本平衡。
hash function 的应用很多，比如说可以用它来写一个字典的程序，很快就可以搜索到需要的词了
binary search tree 也有许多应用，一组数据每一个都有一个priority，和value值，可以很快找到priority最高的值，也可以按照需要查找

评论

发表评论

此博客中的热门博文

Embedded System interview Question

1. What are static variables? Static variable in a function only remain one copy of itself. Static variable in a module can be used by any function in the module Static function can only be called in its class 2.  What are volatile variables? Volatile variables may change its value unexpectedly in the program. The program will check its value every time, it tries to use it. If a variable is not volatile, the program may keep a copy of the var in its cache. 3. What do you mean by const keyword ? A constant variable is a read only variable. You cant change its value else where except initialization. 4. What is interrupt latency? Interrupt latency is the time between the generation of interrupt and the time for interrupt  handler  to process it. 5. How you can optimize it? We may use polling and message passing for interrupt to handle interrupt immediately. 6. What is size of character, integer, integer pointer, character pointer? The size of character is 1 byte, inte
阅读全文

MicroKernel & Exokernel 操作系统未来可能的发展

图片
MicroKernel  可以叫做微内核，有人认为传统的monolithic kernel 提供的东西太多，我们可以给内核减负。 最典型的例子就是L4 micro kernel (图中的kernel)只提供最简单的服务，比如IPC (inter process communication), scheduling, address space  剩下的都交给Server 去处理，Server 类似于传统的monolithic kernel 比如Linux, 但是需要改动,L4 把它改为L4Linux. 源代码修改，此外他们还修改了Windows XP (windows 并非完全的不开源，在授权的情况下可以看到源代码). 修改的目的，很简单：以前Server talks to hardware directly, 现在多加了一层 Kernel (L4),它处理所有的hardware interrupt, 然后作为message 传递给server, server 再传递给software. 比如浏览器process 需要一个network packet。 收到packet 以后,L4 作出interrupt,传给Server(比如L4Linux),Server 再与L4,通过IPC 请求packet内容，L4会map到L4Linux的address space，Server 再传给Software(e.g. Firefox).  再比如page fault（由于内存容量有限，有些内容被暂时swap 到硬盘，application 想用的时候发现不在了，就产生page fault） 产生,首先处理interrupt的是Kernel, Kernel sends IPC to L4Linux, L4Linux从自己manage的physical memory 里面分一个page出来，给application,并更新自己的shadow page table(不是真正的page table) .L4Linux 产生一个返回值告诉L4, 已经完成。L4 updates its true hardware page table. Micro Kernel 从设计之初的想法应该是高效的，反映速度快，因为很多东西都由user space（Micr
阅读全文

中国城市房地产分析

简介 到2018年中国房地产似乎出了大问题，有的地方开始调控政策，海南的限购，西安却开始吸引人才计划，2018年一个季度人口增加30万，3%，房价也随之猛烈上涨。 有的人说房地产要崩盘了，不是政府压着早就破了； 有的人说中国的房地产泡沫不是全局现象，泡沫不大，而且政府控制着不可能破灭，如果政府不控制，涨的更厉害。 政府主流媒体的认为现在买房都是刚需，政府不能让房价迅速上涨。 那么这么多观点究竟谁说的对？ 先分析以下是否是刚需，如果是的话为什么要调控呢？ 刚需指的是需求大，但是供应少。按照市场规律，这时候价格会上涨，供应会随之增加，供应增加以后价格会下降，最终达到一个平衡的状态。所以如果是刚需的话，政府采取的方式应该是提高供应，方法是地方政府批更多，更便宜的地给开发商。但是，政府现在批的地没有增加很多（全国的开工面积是增加的2017 年1.7B平米, 2010年1.6B平米；北京2017年新开工12M平米，2008年11M平米），主要采取的方式是限制贷款，限制购买，和限制价格的三限制政策。 为什么会这样？一种可能是刚需是假的。造成需求大的原因有：人口增长（中国城市化不可避免的，城市人口从10%到60%；资源分配集中在大城市，更多的医疗，学校，工作，基础设施，北京2010年大约20M，现在21M，2000只有13M）；收入增长（收入在过去二十几年里面翻了十倍，有些地方房价也涨了10倍，有的地方涨的更多）；租房价格增长(alternative)（北京租金2016大约71每平米，2018年88每平米， 2008年大约53每平米）。 注意中国的平均数据不能反应各地的实际情况。 拿全国的数据来说，先分析以下需求，首先是人数增长，2013年城镇人口731M, 2017年813M，增长了11%。房地产竣工面积非常稳定大约每年0.7B平米，按照每个城市人均30平米计算，80M的新增人口需要2.4B平米的住房。销售面积每年都超过1B平米，并且统计局表明销售面积不包括二手房，因为期房预售的情况比较普遍，房子还没竣工就卖了。所以等于说这五年卖了超过5B平米的房子，但是需求只有2.4B。 原因之一应该是已有住房的人，想要更多的人均住房面积，住更大的房子。平均到2013年731M的城市人口上每个人增加了3平米，似乎也是合理的。目前城市人均住房面积大约是36平米，2012年32平米，基本和之前估
阅读全文