.NET中哈希表的引用和键的引用分别存在哪

你问题都没说清楚，，，怎么回答你啊？

猜一下吧，你说的键的引用指的是Dictionary吗？

如果是的话，

首先哈希表和Dictionary都是有键和值组成的元素。

他们的区别就在于效率及灵活性上。

从哈希表和Dictionary的Add方法定义来看

HashTable:

public virtual void Add(

Object key,

Object value

)

Dictionary:

public void Add(

TKey key,

TValue value

)

HashTable,的key和value都是object类型的，这样，

HashTable ht=new HashTable();

htAdd(1,12);

这样子就存在一个装箱 *** 作(值类型到引用类型的类型转换)，同样在取值的时候又涉及到拆箱 *** 作(引用类型到值类型的类型转换)装箱和拆箱 *** 作时很费时的 *** 作。在效率上不高。

而Dicitionary是一个泛型类，key及value的类型是在实例化Dictionary对象时指定的，如：

Dictionary<int,int> dict = new Dictionary();

dictAdd(1,12);

同样的 *** 作，但是这里的key和value是在实例化的时候指定的int类型。所以这里不存在装箱和拆箱 *** 作。

以上是Dictionary的优点。

下面是HashTable的优点，Dictionary的缺点。

如果我们所有元素的key和value是相同的类型，使用Dictionary是最好的选择，

但是如过有元素的key和value类型不同的情况下，我们就要使用HashTable了，原因就是HashTable的key和value都是object类型的，而object类型是所有类型的基类。

一下是例子。

HashTable：

HashTable ht = new HashTable();

htAdd(1,12);

htAdd("1","12");

htAdd(2,"12");

htAdd("2",12);

Dictionary实现上面的情况就需要：

Dictionary<int,int> dict = new Dictionary();

dictAdd(1,12);

Dictionary<string,string> dict1 = new Dictionary();

dict1Add("1","12");

Dictionary<int,string> dict2 = new Dictionary();

dict2Add(2,"12")

Dictionary<string,int> dict3 = new Dictionary();

dict3Add("2",12);

以上就是他们的区别了以及各自的优缺点。。。

这个你可以通过对应的Key值来找寻啊 这个时间复杂度为常数

Hashtable hash = new Hashtable();

object o = hash[Key];//通过Key值可以找到Value,如果该Key不存在则返回为null

哈希表：即散列存储结构。

散列法存储的基本思想：建立记录关键码字与其存储位置的对应关系，或者说，由关键码的值决定数据的存储地址。

这样，不经过比较，一次存取就能得到所查元素的查找方法

优点：查找速度极快（O(1)）,查找效率与元素个数n无关！

哈希方法(杂凑法)

选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。

哈希函数(杂凑函数)

哈希方法中使用的转换函数称为哈希函数(杂凑函数)在记录的关键码与记录的存储地址之间建立的一种对应关系

有数据元素序列(14，23，39，9，25，11)，若规定每个元素k的存储地址H（k）＝k ， H(k)称为散列函数,画出存储结构图。

根据散列函数H（k）＝k ，可知元素14应当存入地址为14的单元，元素23应当存入地址为23的单元，……，

根据存储时用到的散列函数H(k)表达式，迅即可查到结果！

例如，查找key=9,则访问H(9)=9号地址，若内容为9则成功；

若查不到，应当设法返回一个特殊值，例如空指针或空记录。

很显然这种搜索方式空间效率过低。

哈希函数可写成：addr(ai)=H(ki)

选取某个函数，依该函数按关键字计算元素的存储位置并按此存放；查找时也由同一个函数对给定值k计算地址，将k与地址中内容进行比较，确定查找是否成功。哈希方法中使用的转换函数称为哈希函数(杂凑函数)在记录的关键码与记录的存储地址之间建立的一种对应关系。

通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，可能将不同的关键码映射到同一个哈希地址上，这种现象称为冲突。

有6个元素的关键码分别为：（14，23，39，9，25，11）。

选取关键码与元素位置间的函数为H(k)=k mod 7

根据哈希函数算出来发现同一个地址放了多个关键码，也就是冲突了。

在哈希查找方法中，冲突是不可能避免的，只能尽可能减少。

所以，哈希方法必须解决以下两个问题：

1）构造好的哈希函数

（a）所选函数尽可能简单，以便提高转换速度；

（b）所选函数对关键码计算出的地址，应在哈希地址内集中并大致均匀分布，以减少空间浪费。

2）制定一个好的解决冲突的方案

查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。

从上面两个例子可以得出如下结论：

哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键码的哈希函数值都落在表长允许的范围之内即可

冲突：key1≠key2，但H(key1)=H(key2)

同义词：具有相同函数值的两个关键码

哈希函数冲突不可避免，只能尽量减少。所以，哈希方法解决两个问题：

构造好的哈希函数；

制定解决冲突基本要求：

要求一：n个数据原仅占用n个地址，虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。

要求二：无论用什么方法存储，目的都是尽量均匀地存放元素，以避免冲突。

Hash(key) = a·key + b (a、b为常数)

优点：以关键码key的某个线性函数值为哈希地址，不会产生冲突

缺点：要占用连续地址空间，空间效率低。

例关键码集合为{100，300，500，700，800，900}，

选取哈希函数为Hash(key)=key/100，

则存储结构（哈希表）如下：

Hash(key)=key mod p (p是一个整数)

特点：以关键码除以p的余数作为哈希地址。

关键：如何选取合适的p？p选的不好，容易产生同义词

技巧：若设计的哈希表长为m，则一般取p≤m且为质数

（也可以是合数，但不能包含小于20的质因子）。

Hash(key)= ⎣ B ( A key mod 1 ) ⎦

(A、B均为常数，且0<A<1，B为整数)

特点：以关键码key乘以A，取其小数部分，然后再放大B倍并取整，作为哈希地址。

例：欲以学号最后两位作为地址，则哈希函数应为：

H(k)=100 (001 k % 1 )

其实也可以用法2实现： H(k)=k % 100

特点：选用关键字的某几位组合成哈希地址。选用原则应当是：各种符号在该位上出现的频率大致相同。

例：有一组（例如80个）关键码，其样式如下：

讨论：

① 第1、2位均是“3和4”，第3位也只有“ 7、8、9”，因此，这几位不能用，余下四位分布较均匀，可作为哈希地址选用。

② 若哈希地址取两位（因元素仅80个），则可取这四位中的任意两位组合成哈希地址，也可以取其中两位与其它两位叠加求和后，取低两位作哈希地址。

特点：对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。(适于不知道全部关键码情况)

理由：因为中间几位与数据的每一位都相关。

例：2589的平方值为6702921，可以取中间的029为地址。

特点：将关键码自左到右分成位数相等的几部分（最后一部分位数可以短些），然后将这几部分叠加求和，并按哈希表表长，取后几位作为哈希地址。

适用于：关键码位数很多,且每一位上各符号出现概率大致相同的情况。

法1：移位法 ── 将各部分的最后一位对齐相加。

法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。

例：元素42751896,

用法1： 427＋518＋96=1041

用法2： 427 518 96—> 724+518+69 =1311

7、随机数法

Hash(key) = random ( key ) (random为伪随机函数)

适用于：关键字长度不等的情况。造表和查找都很方便。

小结：构造哈希函数的原则：

① 执行速度（即计算哈希函数所需时间）；

② 关键字的长度；

③ 哈希表的大小；

④ 关键字的分布情况；

⑤ 查找频率。

设计思路：有冲突时就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。

1）线性探测法

Hi=(Hash(key)+di) mod m ( 1≤i < m )

其中：

Hash(key)为哈希函数

m为哈希表长度

di 为增量序列 1，2，…m-1，且di=i

关键码集为 {47，7，29，11，16，92，22，8，3}，

设：哈希表表长为m=11；

哈希函数为Hash(key)=key mod 11；

拟用线性探测法处理冲突。建哈希表如下：

解释：

① 47、7是由哈希函数得到的没有冲突的哈希地址；

② Hash(29)=7，哈希地址有冲突，需寻找下一个空的哈希地址：由H1=(Hash(29)+1) mod 11=8，哈希地址8为空，因此将29存入。

③ 另外，22、8、3同样在哈希地址上有冲突，也是由H1找到空的哈希地址的。

其中3 还连续移动了（二次聚集）

线性探测法的优点：只要哈希表未被填满，保证能找到一个空地址单元存放有冲突的元素；

线性探测法的缺点：可能使第i个哈希地址的同义词存入第i+1个哈希地址，这样本应存入第i+1个哈希地址的元素变成了第i+2个哈希地址的同义词，……，

因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。

解决方案：可采用二次探测法或伪随机探测法，以改善“堆积”问题。

2） 二次探测法

仍举上例，改用二次探测法处理冲突，建表如下：

Hi=(Hash(key)±di) mod m

其中：Hash(key)为哈希函数

m为哈希表长度，m要求是某个4k+3的质数；

di为增量序列 1^2，-1 ^2，2 ^2，-2 ^2，…，q ^2

注：只有3这个关键码的冲突处理与上例不同，

Hash(3)=3，哈希地址上冲突，由

H1=(Hash(3)+1 ^2) mod 11=4，仍然冲突；

H2=(Hash(3)-1 ^2) mod 11=2，找到空的哈希地址，存入。

3） 若di＝伪随机序列，就称为伪随机探测法

基本思想：将具有相同哈希地址的记录(所有关键码为同义词)链成一个单链表，m个哈希地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的哈希函数为：

Hash(key)=key mod 11，

用拉链法处理冲突，则建表如图所示。

Hi=RHi(key) i=1, 2, …，k

RHi均是不同的哈希函数，当产生冲突时就计算另一个哈希函数，直到冲突不再发生。

优点：不易产生聚集；

缺点：增加了计算时间。

思路：除设立哈希基本表外，另设立一个溢出向量表。

所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的地址是什么，一旦发生冲突，都填入溢出表。

明确：散列函数没有“万能”通式（杂凑法），要根据元素集合的特性而分别构造。

讨论：哈希查找的速度是否为真正的O（1）？

不是。由于冲突的产生，使得哈希表的查找过程仍然要进行比较，仍然要以平均查找长度ASL来衡量。

一般地，ASL依赖于哈希表的装填因子α,它标志着哈希表的装满程度。

0≤α≤1

α 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函数为：H(key)=key MOD 13, 哈希表长为m=16，

设每个记录的查找概率相等

(1) 用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m

(2) 用二次探测再散列处理冲突，即Hi=(H(key)+di) MOD m

(3) 用链地址法处理冲突

1） 散列存储的查找效率到底是多少？

答：ASL与装填因子α有关！既不是严格的O(1)，也不是O(n)

2）“冲突”是不是特别讨厌？

答：不一定！正因为有冲突，使得文件加密后无法破译！（单向散列函数不可逆，常用于数字签名和间接加密）。

利用了哈希表性质：源文件稍稍改动，会导致哈希表变动很大。

在 Redis 中查看数据可以使用以下命令：

keys pattern 命令可以列出匹配给定模式的所有键名。例如，执行 keys 可以列出所有的键名。

type key 命令可以查看指定键的数据类型。例如，执行 type mykey 可以查看键 mykey 的数据类型。

get key 命令可以获取指定键的值。例如，执行 get mykey 可以获取键 mykey 的值。

hgetall key 命令可以获取指定哈希表的所有键值对。例如，执行 hgetall myhash 可以获取哈希表 myhash 的所有键值对。

lrange key start stop 命令可以获取指定列表的一部分元素。例如，执行 lrange mylist 0 -1 可以获取列表 mylist 的所有元素。

smembers key 命令可以获取指定集合的所有成员。例如，执行 smembers myset 可以获取集合 myset 的所有成员。

zrange key start stop 命令可以获取指定有序集合的一部分成员。例如，执行 zrange myzset 0 -1 可以获取有序集合 myzset 的所有成员。

以上是 Redis 中一些基本的数据查看命令，具体使用取决于你想要查看的数据类型和数据结构。

哈希表也叫散列表，是根据键值(Key value)而直接进行访问的数据结构。也就是说，它通过把键(Key)映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，映射函数得出的值叫哈希值或哈希码，存放记录的数组叫做哈希表。哈希表中存放数据占总空间比例叫做装填因子（负载因子）。

哈希函数的设计要达到输出值的平均分布化，这样能尽可能降低哈希冲突的概率。

一般情况下，哈希函数中输入值与输出值具有 N对1 关系。

哈希函数具有的特点：如果两个哈希码不同，则它们的键(Key)也一定不同。

该特点常用于优化比较两个对象是否相同，先判断hash码是否相同，若hash码不同则不需要进行对象比较。

哈希表优点：查找效率高，插入删除和查找时间复杂度为O(1)。

哈希表缺点：占用空间大，需要预留一定空间，否则哈希冲突概率会很大。哈希表无法记录插入顺序。

哈希函数因为会N对1的关系，会触发哈希冲突。哈希冲突常见解决方式有有以下几种：

1 开放寻址法

线性探测（偏移1，2，3）

可能会导致数据堆积一起，降低插入删除和查找效率。

二次方探测（偏移11，22，33）

相比线性探测不容易造成数据堆积，但当装填因子比较大时，可能会造成一次查询/插入中，同一位置多次被探测。

2 拉链法

使用数组+链表解决哈希冲突问题。

开放寻址法缺点：

开放寻址法的缺点是在删除元素时，不能真的删除，否则会引起查找失败。需要在删除元素位置做个标记，代表该索引位置可以插入，但是搜索路过时不能中断搜索。

另一方面，开放寻址法因为在冲突时会占用其它哈希索引空间，所以扩容时装填因子不能太大。

哈希表扩容与缩容

当装填因子过大，会增大哈希冲突概率，需要对哈希表进行扩容，因此哈希表一般使用二级指针实现(iOS底层使用DisguisedPtr<void >）。扩容时需要对所有数据进行重新映射（重哈希），一般每次空间2。

当装填因子太小，且空间占用比较大，比如：if (装填因子 < 01 && num >1024) {缩容}。

哈希算法本质是一类安全性较高的哈希函数。Hash算法还具有一个特点，就是很难找到逆向规律。

哈希算法常用于密码安全领域，哈希算法中输入值与输出值具有 N对1 关系，常见的哈希算法包括MD5，SHA，CRC16，CRC32。

SideTables是个全局变量，是StripedMap（哈希表）类型。

StripedMap重载了[]，可通过下标的方式快速存取。

StripedMap事实上不是个常规的哈希表，我认为它可以叫做只读哈希表。它在创建之初就会以模版类型初始化满所有存储空间，且不支持修改和扩容。因此，模版类型传递指针是没有意义的。一般模版都设置为结构体，后续 *** 作针对该结构体改值。

SideTables的哈希Key是对象地址addr，哈希函数是((addr >>4) ^ (addr >>9)) %StripeCount，Value是SideTable结构体。因此，SideTables存储着对象地址与SideTable的 N-1 关系。这样可以把对象信息分散到不同SideTable中，提升查找效率。

每个SideTable中存储一堆对象的弱引用表和引用计数表。

weak_table_t的哈希Key是对象地址，哈希函数如下：

Value是weak_entry_t。weak_table_t可以通过对象指针快速找到对象存储的weak_entry_t。

weak_table_t可进行扩容与缩容。

当出现哈希冲突时，与weak_table_t配套的函数使用线性探测法查找。

每个weak_table_t中存储一堆对象的弱引用表。

weak_entry_t只有当装载数据超过一定长度才会启用哈希表存储功能，out_of_line()返回是否启用哈希表。weak_entry_t的哈希Key是弱指针地址，value也是弱指针地址。哈希函数与weak_table_t相同。

weak_entry_t可进行扩容，不会进行缩容。

当出现哈希冲突时，与weak_entry_t配套的函数使用线性探测法查找。

每个weak_entry_t存储指向一个对象的所有弱指针地址（二级指针）。

RefcountMap本质是DenseMap类按照指定模版typedef的类型。

RefcountMap的哈希Key是对象地址，Value是引用计数。

当value为0时，RefcountMap会自动清除这条记录。

当出现哈希冲突时，RefcountMap使用二次方探测法查找。

每个RefcountMap中存储一堆对象的引用计数。

sDataLists是存储所有@synchronized锁的全局哈希表，key是@synchronized的参数。

PropertyLocks是存储所有atomic锁的全局哈希表，key是属性生成的成员变量地址。

类对象的方法缓存cache_t使用哈希表存储bucket_t（sel+imp)，使用逆序线性探测（Index-1)解决哈希冲突。

cache_t扩容时会将所有方法缓存清空。

static objc::ExplicitInitDenseSet<const char > namedSelectors;

namedSelectors是个全局变量，存储所有的方法名SEL，内部结构是哈希表DenseMap。

typedef DenseMap<DisguisedPtr<objc_object>, ObjectAssociationMap> AssociationsHashMap;

AssociationsHashMap是AssociationsManager中存储所有关联对象的哈希表，内部结构是DenseMap。

NSObject默认的hash方法是对象地址，即默认没有做优化。

还有个方法isEqual:方法，NSObject默认实现返回该对象与参数对象指针地址是否相同。

hash方法的本质是该对象的哈希函数，需要子类去实现。hash方法主要有两个作用，这两个作用在NSDictionary和NSSet中体现出来。

1 与isEqual:配合，优化比较

先调用hash方法进行比较，若值相同才调用isEqualTo:进行比较。这依赖于hash的 N-1 关系。

从CF源码中可以找到CFString的源码，即可以看到NSString内部重写的hash方法。

这句话的大意是：这个字符串的大小如果小于等于96，则保证哈希的安全；如果大小大于96，则会大幅度增加哈希冲突的概率。

2 与哈希表配合，hash方法对应哈希表的哈希函数，但返回值需要经过转换对应存储索引（一般通过取余）。此时hash方法的设计就非常重要，应做到输出哈希码的平均分散化，否则会导致数据堆叠，增大哈希冲突概率。

常见的NSDictionary和NSSet内部就是哈希表，NSDictionary会使用Key作为哈希表的Key，NSSet使用元素作为Key。它们会对Key对象调用hash方法获得初步的哈希码，然后经过转变成为存储区域的索引（下标）。

NSDictionary和NSSet因为都使用哈希表存储，因此存储元素都是无序的。

NSDictionary和NSSet在插入新元素时具体步骤如下：

以上就是关于.NET中哈希表的引用和键的引用分别存在哪全部的内容，包括:.NET中哈希表的引用和键的引用分别存在哪、c# 怎么读取hashtable某一个键的值、哈希表详解等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！