Remarks: By default, we show e-Lecture Mode for first time (or non logged-in) visitor.
Please login if you are a repeated visitor or register for an (optional) free account first.
Pro-tip: Since you are not logged-in, you may be a first time visitor who are not aware of the following keyboard shortcuts to navigate this e-Lecture mode: [PageDown] to advance to the next slide, [PageUp] to go back to the previous slide, [Esc] to toggle between this e-Lecture mode and exploration mode.
Another pro-tip: We designed this visualization and this e-Lecture mode to look good on 1366x768 resolution or larger (typical modern laptop resolution in 2017). We recommend using Google Chrome to access VisuAlgo. Go to full screen mode (F11) to enjoy this setup. However, you can use zoom-in (Ctrl +) or zoom-out (Ctrl -) to calibrate this.
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
假设我们有一个大小为 M 的散列表,其中键用于标识卫星数据,并且使用特定的散列函数来计算散列值。 使用散列函数从键v计算键v的散列值/散列码以获得范围从0到M-1的整数。 该散列值用作卫星数据的散列表条目的基址/归位索引/地址。
X Esc
上一个 PgUp
下一个 PgDn
X Esc
上一个 PgUp
下一个 PgDn
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
人们已经尝试过各种方法,尽可能均匀地将大范围的整数散列到更小范围的整数中。 在这个电子讲座中,我们直接跳到最好的和最受欢迎的版本之一:h(v)= v%M,即将v 映射到大小为M个时隙的散列表中。 (%)是一个模运算符,给出了除法后的余数。 这显然很快,即O(1)假设v不超过自然整数数据类型限制。 哈希表大小M被设置为不接近2的幂的相当大的素数,大约比将在哈希表中使用的期望的键的数量N大2倍以上。 这样,负载因子α= N / M <0.5 — 稍后我们将看到具有低负载因子,从而牺牲空闲空间,有助于提高哈希表性能。 讨论:如果我们将M设置为10(十进制)的幂或2(幂的二进制),那该怎么办?
X Esc
上一个 PgUp
下一个 PgDn
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
int hash_function(string v){//假设1:v仅使用['A'..'Z'] int sum = 0; //假设2:v是一个短字符串 for(auto&c:v)//对于v中的每个字符c sum =((sum * 26)%M +(c - 'A' + 1))%M; // M是表格大小 return sum; } 讨论:在现实生活中,讨论上面散列函数的组成部分,例如 为什么循环遍历所有字符?,会比O(1)慢吗?为什么要用26来乘?,如果字符串v使用的不仅仅是大写字符?,等等
X Esc
上一个 PgUp
下一个 PgDn
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
分离链接法(SC)冲突解决技术很简单。 我们使用 M 个副本数据结构副本,通常是双向链接列表。 如果两个键 a 和 b 都具有相同的散列值 i,则两个键都将被附加到双链表 i 的(前/后)(在该可视化中,我们借助尾指针,用O(1)的时间将它附加到后面)。 就是这样,键(keys)将被插入的地方完全依赖于散列函数本身,因此我们也称分离链接法为封闭寻址冲突解决技术。
如果我们使用分离链接法,负载因子α= N / M描述了M个列表的平均长度,它将决定搜索的性能(v),因为我们可能需要平均探索α个元素。 由于删除(v) - 也需要搜索(v),其性能与搜索(v)相似。 插入(v)显然是O(1)。 如果我们可以将α限制为一个小常量,则使用分离链接法的所有搜索(v),插入(v)和删除(v)操作都将为O(1)。
X Esc
上一个 PgUp
下一个 PgDn
查看上面的哈希表的可视化。
在这个可视化中,我们防止重复键的插入。
由于屏幕大小限制,散列表尺寸被限制为M=19。
哈希表在水平方向上可视化为一个数组,其中指数0放置在最左边,指数M-1放置在最右边,但是当我们可视化开放寻址 vs 分离链接冲突解决方法时,细节会有不同。
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
However, if you ever need to implement a Hash Table in C++ or Java and your keys are either Integers or Strings, you can use the built-in C++ STL or Java API. They already have good built-in implementation of default hash functions for Integers or Strings.
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
e-Lecture: The content of this slide is hidden and only available for legitimate CS lecturer worldwide. Drop an email to visualgo.info at gmail dot com if you want to activate this CS lecturer-only feature and you are really a CS lecturer (show your University staff profile).
X Esc
上一个 PgUp
下一个 PgDn
使用用户控件控制动画!可用的快捷键有:
空格键:绘制/停止/重绘
左/右箭头:上一步/下一步
-/+:减缓/增加速度
X Esc
上一个 PgUp
下一个 PgDn
Return to 'Exploration Mode' to start exploring!
Note that if you notice any bug in this visualization or if you want to request for a new visualization feature, do not hesitate to drop an email to the project leader: Dr Steven Halim via his email address: stevenhalim at gmail dot com.
项目领导和顾问(2011年7月至今) Dr Steven Halim, Senior Lecturer, School of Computing (SoC), National University of Singapore (NUS) Dr Felix Halim, Software Engineer, Google (Mountain View)