争取能在百度搜索到把青春献给代码的你;一个年轻程序员的渺小梦想-杨永飞
NOTES DETAIL
哈希算法,根据key生成hashcode,hashcode与value映射,key是唯一的,有n个key就有n个hashcode,现有key1需要查询计算出hashcode1,在那么多hashcode中找出hashcode1也需要很多时间,这跟二维数组有什么区别?如果说hashcode值是数组下标,假设key1对应的hashcode1值为x,key2对应的hashcode2值为10000x,中间岂不是空了很多下标?
 紫幽情儿        1005
哈希表可以理解为一维数组。因为只是单一的坐标。当然如果考虑到哈希碰撞,理解为二维数组也无不可。

至于下标1跟10001,这个问题很好。你观察到了,这样的数组会有大量的空洞。这是一种常见的现象。

一维的这种数组叫做稀疏数组,二维的这种数组叫做稀疏矩阵。而对稀疏数组跟稀疏矩阵都有专门的保存算法。

从数学角度,哈希表可能是个稀疏数组,或者如果你认为它是二维的话,那就是个稀疏矩阵,如果这样的话,在存取时,它往往需要用专门的办法优化其存储占用。

不过,在实际的工程中,一个好的散列函数会尽可能的让其存储均匀分布,不褪变成稀疏数组而是保持成为普通数组,如此一来,可以通过选择良好的散列函数避免存储稀疏数组的开销,这也算是散列函数选择的技巧了。

不要把抽象的数据结构跟其实现混为一谈。

一维数组,可以是线性表,也可以是向量,也可以是一维矩阵。

二维数组,可以是二维矩阵,也可以是作为某种其他结构的内部存储。

哈希表,可以用来实现键值对结构,也可以用来实现集合。而键值对或集合也可以用树来实现。

所属标签: 笔记

0 条评论

既来之,说两句吧!

关于我

莫失莫忘,莫惆怅,莫提前生,莫妄后生。知人,知世事,自知,知余于心,力不逮~~

1根小腿毛

浏览最多

话剧《命运之影》如何再现诺

2018-06-25

暂时没有任何描述哦~

上海国际艺术节|纪

2018-06-25

陈冠希,一直在音乐

2018-06-25

照片墙

文件下载

  • 贝壳云笔记mac版本

    [ 1 ]

  • 判断移动端设备并且跳转

    [ 1 ]

  • 自适应图片大小

    [ 1 ]

  • 截图定位软件

    [ 0 ]

  • ps破解版小体积

    [ 0 ]

  • 注册表单密码验证提示代码

    [ 0 ]