【哈希表是什么】哈希表、字典、二维数组的区别是什么?

2019-12-17 - 哈希表

先不要管hash不hash,我们先把你所提到的这些数组呀哈希表呀都描述成函数f(x...)。这些函数接受不同的参数(具体分析),而都是返回一个内存地址。 f(x...)表示f可能接受多个参数 为了方便起见,这里的内存地址统一以十进制表示,以0开始。

【哈希表是什么】哈希表、字典、二维数组的区别是什么?
【哈希表是什么】哈希表、字典、二维数组的区别是什么?

===== 定义: f(x...)表示一个内存地址 g(f(x...))=a表示向一个内存地址写入值a ===== 我们来探讨一下这些函数的差异。例如我们要将数据a存储到f(x...)里(再次注意这个fx指的是内存地址)

首先我们看看(朴素的)二维数组。准确地来说叫二维表(table),因为数组并不是一个数据结构。定义一个二维数组arr[20][20]。 我们在存储数据的时候会想要有各种各样的存储办法,比如选择一个“坐标”(x,y),而这个存储“办法”实际上决定了数据的存储位置f(x,y),于是 f(x,y)=x*20 y g(f(x,y))=a 然而,我们如果又想找到a,又忘记了刚才的x和y两个参数,这时候我们就得挨个试一遍x和y,这样我们最多得试400次,也就是书本上所说的O(n^2)

【哈希表是什么】哈希表、字典、二维数组的区别是什么?
【哈希表是什么】哈希表、字典、二维数组的区别是什么?

接下来看哈希表。我们从刚才想要解决的任务开始看起:找到我刚才存在这一大片内存里的a。 不难发现,我们刚才很难找到a的问题出在了我们的存储方式上。由于我们的存储方式跟a本身毫无关联,我们基本上就是在瞎找。

【哈希表是什么】哈希表、字典、二维数组的区别是什么?
【哈希表是什么】哈希表、字典、二维数组的区别是什么?

所以我们如果要有目的地找到a,最好的办法是把存a的位置跟a本身联系在一起。 于是有: f(a)=h(a) g(f(a))=a <del>注意,这里的h(a)并没有其他意思<\del> 注意,h(a)表示一个固定的函数,比如h(a)=a 这样的话,我们要找到a,可以说是得来全不费功夫了,因为我们可以很确定地说:“a存在h(a)处,因为f(a)=h(a)。

【哈希表是什么】哈希表、字典、二维数组的区别是什么?

”这就是书上的O(1)。 恭喜,h(a)即hash(a),哈希函数。

字典的实现可以是多种多样的,哈希是很好的一个实现手段。只不过,我们在记下a的同时,要在a上绑定一个b,这样我们在找到a的时候同时也找到了b。 但是字典更常用的实现手段是树。 这就涉及到树形结构了。在说树形结构之前,我先说说链表

链表之所以存在,是因为在实际的应用实践中,数组在申请之时就必须固定下来它的长度。为了实现“变长数组”,除了暴力重申请vector大法,就是链表了。 链表的每个元素都是独立存在于内存中的一部分。(散乱分布于赤道板上23333)要将它们联系起来,串成一个长长的链,我们就得让每个元素都记一下“我后面的人的位置”,就像排队一样。

每个人不需要记住整个队列,只要记住后面是谁,或者前面是谁,或者前后都记一下,就可以了。 很遗憾,由于每个人都只记了前后,所以我们如果要找到a,还得一个人一个人地找过去。

所以才有了树啊

树的定义就不赘述了。 手机码的,让我歇一会,过会写 ================== mmp 又没人看,不写了

================== 真的有人看啊。。。好吧继续写一些

树可以这么理解: 构建一个链表,然后把一些元素记住的人改成别人记过的人。

我们先看看相比于链表,这个树有什么不同。 树中的每个单独元素跟链表并没有多大的区别,但是其间的连接方式有所不同。链表的元素只能***被指向***一次,而树中的元素可以被指向多次。 这样有什么好处呢?为了实现检索的功能(检索a),我们先把这个树做一些小小的改动

观察一下 “说好的一个人只记前面的人呢???” 如果用前一种方式存储一棵树,那么不难发现,第二层,第三层的人对于上一层的人来说都是一样的,这样就失去了整个集合的有序性,就是说第二,三层的人不能确定自己到底站在左面好还是中间好。 如果让上一层的人来记下一层的人,那么就可以对他们说,“a站我左下方,b站中间(bilibili )”这样就有秩序(fgo)了。

作为二进制的计算机,最常用的树便是二叉树了。这样的树的每个人都能记住两个人。

==//满二叉树

好了,我们快步来到了排序树的门前,马上就能找到a了 为了整齐,我们让每人都记住:如果有人想站你后面,你看看他的个子。如果这个人个子比你高,那么你让他站你左面,如果这个人个子比你矮,你让他站你右面。如果你左面或者右面已经站了一个人,你让这个人再找你后面的人去理论一番。

每当我们叫一个人站进队伍里,我们都得让他找最初站在队里的人。这个人被我们任命为队长,也就是平时所说的“树根”(root)(参考上面那个神奇的图)

好了,我们来讲我们说的那一大堆转化为数学。 不难看出,a所在地址和\a的个子/和\队长是谁/有强烈的关系。这个关系看起来是这样的:

而g(f(a,a所在队伍的队长))=a 如果这个队伍比较紧凑,那么我就可以相对容易地找到a,比如在这个有18个人的队伍里,我只用找4次就能找到a

而在下面这个队伍里,我最多要找18次才能找到a

就很气。 所以说,一个(朴素的)二叉排序树带来的查询(插入)均摊复杂度是O(log(2,n)到(n)之间的某个数)←瞎编的 顺带说一句,由于一颗树的第i层有2^(i-1)个节点(元素),所以树高最小为log(2,n)

那么,有没有什么办法让一个排序树的复杂度稳定在O(log(2,n))附近呢? (待续,写作业去了

相关阅读
  • 【数据结构哈希表例题】简单易懂数据结构之哈希表

    【数据结构哈希表例题】简单易懂数据结构之哈希表

    2019-12-17

    Hash表被称作哈希表,也叫做散列表。哈希表是一种比较特殊的数据结构,它遵循函数映射的思想,以Key Value的方式存储数据。哈希表最大的特点是可以快速定位到要查找的数据,查询的时间复杂度接近O(1)。

  • 【哈希表示意图】哈希表的一些知识点

    【哈希表示意图】哈希表的一些知识点

    2019-12-17

    在编程的世界中,比较重要的数据结构有以下3个我们都知道,数组是存储数据的天然载体,在内存中是一段连续的地址,正是由于这个特性,我们能够通过数组的下标快速的获取与之对应的value。本质上是通过下标来计算出value的内存地址。

  • 【异食癖心理】印度26岁女子患有异食癖 吞下2.7斤珠宝与硬币

    【异食癖心理】印度26岁女子患有异食癖 吞下2.7斤珠宝与硬币

    2019-12-09

    据《每日邮报》7月25日报道称,当地时间7月16日,印度女子鲁妮哈通(Runi Khatun)因身体虚弱被紧急送往当地医院,经手术,医生从她的腹中取出总重3磅(约2.7斤)的珠宝和硬币,这些珠宝价值约53。