某企业网站建设方案,设计模板选项是用来,无锡建网站价格,苏州专业建站参考资料#xff1a;
.Net 中HashTable#xff0c;HashMap 和 Dictionarykey,value 和ListT和DataTable的比较 - 王若伊_恩赐解脱 - 博客园
c#HashSet源码解析_fdyshlk的博客-CSDN博客_c# hashset
红黑树和哈希表的区别 - 安全技术 - 亿速云
一、基本概念…参考资料
.Net 中HashTableHashMap 和 Dictionarykey,value 和ListT和DataTable的比较 - 王若伊_恩赐解脱 - 博客园
c#HashSet源码解析_fdyshlk的博客-CSDN博客_c# hashset
红黑树和哈希表的区别 - 安全技术 - 亿速云
一、基本概念
Hash和红黑树是两种数据存储的方式。除了这两种存储方式最常用的是线性结构存储比如数组和链表List等线性结构。
对于线性存储的数据如果想检索一个数据需要把所有数据都遍历一遍然后找到你所需要的数据。这种方式对于大数据而言效率极低其时间复杂度为O(n)。
二、哈希和红黑树基本原理
哈希hash也称散列通过散列算法变成固定的输出到数组所有的线性数据结构中数组的定位速度最快因为它可通过数组下标直接定位到相应的数组空间就不需要一个个查找。
红黑树的自旋是天才的设计是一种特殊的平衡二叉树数据结构特点也是从几十万的数据里面几步就能查找到速度快。
三、使用场景
1、速度对比 物联网可能是数百万设备或者用户联网对高并发要求很大所以对网络安全产品第一要求的是性能和速度。总体来说哈希查找速度会比红黑树快而且查找速度基本和数据量大小无关属于常数级别;而RB树的查找速度是log(n)级别。 红黑树查找和删除的时间复杂度都是O(logn)Hash查找和删除的时间复杂度都是O(1)。 如果红黑树的树高度不深如小于8采用的是数字查找两者性能没有太多的差异。 也就是并非所有的场景哈希都比红黑树快要看代码的优化程度。hihttps使用的linux高并发EPOLL模式事件管理就是红黑树。
2、数据预知 静态数据可以基本预知大小用哈希。如t初始化的规则就几百条在可控范围内另外TOPIC黑白名单、URL地址等也不会太多也是用的哈希就可以了。 动态数据如统计IP地址、任务调度、epoll高并发事件管理无法判断多少可能很少也可能巨多用红黑树更佳。当然如果大概知道设备IP地址数量在一定范围如只有几千完全也可以用哈希。
3、内存消耗 对内存要求严格的地方如嵌入式系统用红黑树。红黑树占用的内存更小仅需要为其存在的节点分配内存而哈希事先就应该分配足够的内存存储散列表浪费内存。 对内存消耗无所谓的地方如服务器有巨大的内存用哈希。哈希最大的缺点是内存分配得小可能元素就会冲突冲突的元素大于8个成链表效率还不如红黑树。 Java 的hashmap就是把哈希和红黑树结合在以前的。当同一个hash值的节点数不小于8时不再采用单链表形式存储而是采用红黑树。
4 复杂程度 哈希更简单红黑树算法复杂一点不过这都不是事大神早开源了很多稳定的版本。
四、应用场景总结 红黑树是有序的哈希是无序的根据项目需求来选择阿里巴巴的很多项目用红黑树更多笔者认为主要还是和内存有关如果内存要求苛刻的项目就用红黑树如果内存足够大牺牲内存换取更快的速度哈希完全适合。 Hiihttps开源waf大量采用哈希算法可能和速度并发要求有关。总之数据结构是网络安全最基础的学科。 五、C#中的应用HashTable和Dictionary
首先在.Net 模仿java 的过程中 抛弃了 HashMap 所以以后再去面试.Net的时候当别人问你HashTable 和HashMap 的区别的时候请告诉他C#.Net 中 没有HashMap。同时C#中也没有Java中的TreeMap和TreeSet即底层是由红黑树实现的数据结构
HashTable 和 Dictionary
数据结构
Hashtable和Dictionary从数据结构上来说都属于Hashtable哈希表都是对关键字键值进行散列操作将关键字散列到Hashtable的某一个槽位中去不同的是处理碰撞的方法。散列函数有可能将不同的关键字散列到Hashtable中的同一个槽中去这个时候我们称发生了碰撞为了将数据插入进去我们需要另外的方法来解决这个问题。 采用链表法的是Dic 而采用开放寻址法(open addressing)-中 双重散列的方法的是 HashTable
至于这两种数据结构的使用方法 请自行阅读算法导论 或者参照网上博客
但从底层的数据结构可以发现
如果增删的动作很多的话 推荐使用Dic 因为解决碰撞的方式 是List.Add
如果改动的动作很少 查询的动作很多的话 则推荐 使用HashTable 因为映射查找之后 只需要跳跃查找到 碰撞后移动数据即可另外当增加数据太多时开放寻址的扩容很耗费性能请阅读算法导论
Dic 和HashTable使用比较
单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分.多线程程序中推荐使用 Hashtable, 默认的 Hashtable 允许单线程写入, 多线程读取, 对 Hashtable 进一步调用 Synchronized() 方法可以获得完全线程安全的类型. 而 Dictionary 非线程安全, 必须人为使用 lock 语句进行保护, 效率大减.Dictionary 有按插入顺序排列数据的特性 (注: 但当调用 Remove() 删除过节点后顺序被打乱), 因此在需要体现顺序的情境中使用 Dictionary 能获得一定方便. //Dic遍历时 会采用插入时的遍历而hashTable 采用遍历时 则是打乱的
Hashtable 类和 DictionaryTKey, TValue 泛型类实现 IDictionary 接口 DictionaryTKey, TValue 泛型类还实现 IDictionaryTKey, TValue泛型接口。 因此这些集合中的每个元素都是一个键/值对。
DictionaryTKey, TValue 类与 Hashtable 类的功能相同对于值类型特定类型不包括 Object的 DictionaryTKey, TValue 的性能优于 Hashtable这是因为 Hashtable 的元素属于 Object 类型所以在存储或检索值类型时通常发生装箱和取消装箱操作。
Dic 和 ListT
关于数据结构
在前边的比较已经介绍了Dic 那么 List T 的数据结构是什么样子的
ListT是 ArrayList 的泛型等效类(继承了泛型接口)
堆中的样子是这样的 我们为了讨论遍历时Dictionary和List的效率有个高人写了个代码这是载图 很明显LIST效率要好的多。
问题剖析
同样是集合为什么性能会有这样的差距。我们要从存储结构和操作系统的原理谈起。
首先我们清楚ListT是对数组做了一层包装我们在数据结构上称之为线性表而线性表的概念是在内存中的连续区域除了首节点和尾节点外每个节点都有着其唯一的前驱结点和后续节点。我们在这里关注的是连续这个概念。
而HashTable或者Dictionary他是根据Key而根据Hash算法分析产生的内存地址因此在宏观上是不连续的虽然微软对其算法也进行了很大的优化。
由于这样的不连续在遍历时Dictionary必然会产生大量的内存换页操作而List只需要进行最少的内存换页即可这就是List和Dictionary在遍历时效率差异的根本原因。
所以根据value 的查找 dic 的效率是高于 List 的 但是遍历的话 则Dic 要差点。这就好比你要摘抄书里边的所有文字 是根据目录 查一个找一篇文章 快还是直接从正文开始 从头到尾快遍历快一样。单独的找某一篇知道题目(key)的文章 当然是从目录快了
再谈Dictionary
也许很多人说既然Dictionary如此强大那么我们为什么不用Dictionary来代替一切集合呢
在这里我们除了刚才的遍历问题还要提到Dictionary的存储空间问题在Dictionary中除了要存储我们实际需要的Value外还需要一个辅助变量Key这就造成了内存空间的双重浪费。
而且在尾部插入时List只需要在其原有的地址基础上向后延续存储即可而Dictionary却需要经过复杂的Hash计算这也是性能损耗的地方。
延伸SortedList和SortedDictionary
SortedDictionaryTKey, TValue泛型类是检索O(log n)的二叉搜索树其中n是字典中的元素数。在这里它类似于SortedListTKey, TValue泛型类。这两个类有相似的对象模型并且都有O(log n)检索。这两个类的不同之处在于内存的使用以及插入和删除的速度: SortedListTKey, TValue比SortedDictionaryTKey, TValue 使用更少的内存. SortedDictionaryTKey, TValue对于未排序的数据O(log n)具有更快的插入和删除操作而SortedListTKey, TValue的插入和删除都是O(n) 如果列表是由已排序的数据一次填充的那么SortedListTKey, TValue要比SortedDictionaryTKey, TValue快。
两者基本叙述
SortedList是一个已序的数组基于KeyValuePair的数组。基于键值排序的键值对数组使用二分查找(log n)检索key也可根据index检索(log 1)add和remove都是o(n)。SortedList为了保持数组的排序它会移动位于插入的元素位置之后的所有元素使用Array.Copy(),由于每次的插入都会重新排序导致插入时的性能很差因此并不推荐使用SortedList排序一个数组。SortedDictionary: 是一个BST基于二叉查找树实现使用二分查找检索(key)add和remove都是o(log n)
延伸2 c#中的数组、ArrayList、List区别
https://www.cnblogs.com/newcapecjmc/p/6970220.html
