c – 为什么python的dict被实现为哈希表,而std :: map是基于树的？

原文

为什么一种语言使用树,另一种使用哈希表来看似相似的数据结构？

c的地图vs python的dict

一个相关的问题是关于哈希表的性能.
请评论我对哈希表的理解.

树保证有O(log n).
而哈希表无法保证,除非由于可​​能的冲突而事先知道输入.
我倾向于认为随着问题的大小越来越多,哈希表的性能将会接近O(n).
因为我没有听说过随着问题大小的增长动态地调整表格大小的哈希函数.

因此,散列表仅对某些特定范围的问题大小有用,这就是为什么大多数DB使用树比哈希表.

解决方法

新的C标准的std :: unordered_map类型为 which is a hash table. IIRC他们希望它达到以前的标准,但在讨论中没有足够的时间被遗漏.然而,大多数流行的编译器多年来一直以这种方式提供.

换句话说,别担心太多了.使用正确的数据结构来完成任务.

至于你对哈希表的理解,这是不准确的：

I haven’t heard of a hash function that dynamically adjust its table
size as problem size grows

所有严格的散列表实现通过分配更大的数组并重新对所有的键重新进行动态调整.虽然这个操作是昂贵的,如果设计得当(要做的很少),表现仍然是摊销O(1).

c – 为什么python的dict被实现为哈希表,而std :: map是基于树的？的更多相关文章

  1. swift篇第一期：简单的数据结构

    首先我们可以去使用Playground来编码，并且会实时的显示对应的编码信息，这样我们就不用每次都去运行程序来显示输出的东西了哦，也方便了我们对某些语句的验证，这个是比较赞的var与let前者为可变修饰符，后者为不可变从字面意思我们就可以很好的区分了常用的类型呢，跟其他语言基本相同啦，主要有几种：1.int类型2.Float,Double类型3.String类型4.Boolean类型当我们去声明一

  2. Swift 集合数据结构性能分析

    本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至dio@foxmail.com举报，一经查实，本站将立刻删除。

  3. Swift中的集合类数据结构

    在那种情况下，你将会需要一种基本的集合类数据结构。继续学习，你将会比较成熟的Cocoa数据结构与对应的纯Swift结构的性能。常见iOS数据结构iOS中三种最常用的数据结构是arrays，dictionaries和sets。除了在Swift和Objective-C中旧的Foundation框架中的数据结构，现在又有了新的仅支持Swift版本的数据结构与语言紧密结合在一起。Swift数组是同质的，意味着每一个Swift数组都只包含一种类型的对象。

  4. 《Swift NSDictionary 的详细使用和部分方法介绍 和 哈希表散列)的阐述和解释 》

    /*《SwiftNSDictionary的详细使用和部分方法介绍和哈希表（散列)的阐述和解释》*//*第一步：我们首先，必须了解一个概念性的东西那就是：哈希哈希的主要解释是：哈希算法将任意长度的二进制值映射为较短的固定长度的二进制值，这个小的二进制值称为哈希值。2》哈希列表是跟进式变化的。作为线性数据结构与表格和队列等相比，哈希表无疑是查找速度比较快的一种。在哈希方法中使用的转换函数hash被称作哈希函数。按照此中算法构造出来的表叫做哈希表。

  5. 11.Swift 中的类和结构体

    举例来说，以下情境中适合使用结构体：1.几何形状的大小，封装一个width属性和height属性，两者均为Double类型。这次就讲到这里,下次我们继续

  6. a place you can learn algorithms and data structures(算法和数据结构) in swift

    https://github.com/raywenderlich/swift-algorithm-club

  7. Swift3.0 类和结构体的选择

    结构体实例总是通过值传递，类实例总是通过引用传递先说说值类型和引用类型的区别值类型被赋予给一个变量、常量或者被传递给一个函数的时候，其值会被拷贝在Swift中，所有的结构体和枚举类型都是值类型。实际中，这意味着绝大部分的自定义数据构造都应该是类，而非结构体”Swift中，许多基本类型，诸如String，Array和Dictionary类型均以结构体的形式实现。Objective-C中Nsstring，NSArray和NSDictionary类型均以类的形式实现，而并非结构体。

  8. Swift 中“等同性”、“比较”、“哈希” 概念理解

    甚至某些场景下还需要将其作为键值对中的Key，这就涉及到哈希函数以及哈希值的碰撞问题了。不过仔细查看代码，我们会发现上诉冲突的原因之一就是name、capital属性采用了同样的哈希函数。并修改Country中的哈希实现：改进后上诉冲突得以解决：总结本文简单的介绍了Swift中“等同性”、“比较”、“哈希”的概念，并对一些常见哈希冲突进行了分析。

  9. 【Swift】结构体和类

    Swift中结构体和类有很多共同点与结构体相比，类还有如下的附加功能:结构体和枚举是值类型值类型被赋予给一个变量、常量或者被传递给一个函数的时候，其值会被拷贝。为了达到这个目的，Swift内建了两个恒等运算符:类和结构体的选择在你的代码中，你可以使用类和结构体来定义你的自定义数据类型。实际中，这意味着绝大部分的自定义数据构造都应该是类，而非结构体。Swift中，许多基本类型，诸如String，Array和Dictionary类型均以结构体的形式实现。

  10. 如何在Swift中创建打包数据结构？

    我正在将一个项目从Objective-C转换为Swift,我正在使用一个打包的结构来输入通过套接字发送的转换二进制消息：我不确定Swift中最好的方法是什么,我能得到的最接近的近似值是：翻译中丢失了两个重要的细节：没有保证整数类型的比特,并且没有结构打包.我不认为这可以在Swift中表达,但如果是这样,怎么样？

随机推荐

  1. 从C到C#的zlib(如何将byte []转换为流并将流转换为byte [])

    我的任务是使用zlib解压缩数据包(已接收),然后使用算法从数据中生成图片好消息是我在C中有代码,但任务是在C#中完成C我正在尝试使用zlib.NET,但所有演示都有该代码进行解压缩(C#)我的问题：我不想在解压缩后保存文件,因为我必须使用C代码中显示的算法.如何将byte[]数组转换为类似于C#zlib代码中的流来解压缩数据然后如何将流转换回字节数组？

  2. 为什么C标准使用不确定的变量未定义？

    垃圾价值存储在哪里,为什么目的？解决方法由于效率原因,C选择不将变量初始化为某些自动值.为了初始化这些数据,必须添加指令.以下是一个例子：产生：虽然这段代码：产生：你可以看到,一个完整的额外的指令用来移动1到x.这对于嵌入式系统来说至关重要.

  3. 如何使用命名管道从c调用WCF方法？

    更新：通过协议here,我无法弄清楚未知的信封记录.我在网上找不到任何例子.原版的：我有以下WCF服务我输出添加5行,所以我知道服务器是否处理了请求与否.我有一个.NET客户端,我曾经测试这一切,一切正常工作预期.现在我想为这个做一个非托管的C客户端.我想出了如何得到管道的名称,并写信给它.我从here下载了协议我可以写信给管道,但我看不懂.每当我尝试读取它,我得到一个ERROR_broKEN_P

  4. “这”是否保证指向C中的对象的开始？

    我想使用fwrite将一个对象写入顺序文件.班级就像当我将一个对象写入文件时.我正在游荡,我可以使用fwrite(this,sizeof(int),2,fo)写入前两个整数.问题是：这是否保证指向对象数据的开始,即使对象的最开始可能存在虚拟表.所以上面的操作是安全的.解决方法这提供了对象的地址,这不一定是第一个成员的地址.唯一的例外是所谓的标准布局类型.从C11标准：(9.2/20)Apointe

  5. c – 编译单元之间共享的全局const对象

    当我声明并初始化一个const对象时.两个cpp文件包含此标头.和当我构建解决方案时,没有链接错误,你会得到什么如果g_Const是一个非const基本类型！PrintInUnit1()和PrintInUnit2()表明在两个编译单元中有两个独立的“g_Const”具有不同的地址,为什么？

  6. 什么是C名称查找在这里？ (&GCC对吗？)

    为什么在第三个变体找到func,但是在实例化的时候,原始变体中不合格查找找不到func？解决方法一般规则是,任何不在模板定义上下文中的内容只能通过ADL来获取.换句话说,正常的不合格查找仅在模板定义上下文中执行.因为在定义中间语句时没有声明func,并且func不在与ns::type相关联的命名空间中,所以代码形式不正确.

  7. c – 在输出参数中使用auto

    有没有办法在这种情况下使用auto关键字：当然,不可能知道什么类型的.因此,解决方案应该是以某种方式将它们合并为一个句子.这可用吗？解决方法看起来您希望默认初始化给定函数期望作为参数的类型的对象.您无法使用auto执行此操作,但您可以编写一个特征来提取函数所需的类型,然后使用它来声明您的变量：然后你就像这样使用它：当然,只要你重载函数,这一切都会失败.

  8. 在C中说“推动一切浮动”的确定性方式

    鉴于我更喜欢将程序中的数字保留为int或任何内容,那么使用这些数字的浮点数等效的任意算术最方便的方法是什么？说,我有我想写通过将转换放在解析的运算符树叶中,无需将表达式转化为混乱是否可以使用C风格的宏？应该用新的类和重载操作符完成吗？解决方法这是一个非常复杂的表达.更好地给它一个名字：现在当您使用整数参数调用它时,由于参数的类型为double,因此使用常规的算术转换将参数转换为double用C11lambda……

  9. objective-c – 如何获取未知大小的NSArray的第一个X元素？

    在objectiveC中,我有一个NSArray,我们称之为NSArray*largeArray,我想要获得一个新的NSArray*smallArray,只有第一个x对象…

  10. c – Setprecision是混乱

    我只是想问一下setprecision,因为我有点困惑.这里是代码：其中x=以下：方程的左边是x的值.1.105=1.10应为1.111.115=1.11应为1.121.125=1.12应为1.131.135=1.14是正确的1.145=1.15也正确但如果x是：2.115=2.12是正确的2.125=2.12应为2.13所以为什么在一定的价值是正确的,但有时是错误的？请启发我谢谢解决方法没有理由期望使用浮点系统可以正确地表示您的帖子中的任何常量.因此,一旦将它们存储在一个双变量中,那么你所拥有的确切的一

返回
顶部