程序员哈希表是什么

❶ 面试中如何回答HashMap的工作原理

用过哪些Map类，都有什么区别，HashMap是线程安全的吗,并发下使用的Map是什么，他们
内部原理分别是什么，比如存储方式，hashcode，扩容，默认容量等。
JAVA8的ConcurrentHashMap为什么放弃了分段锁，有什么问题吗，如果你来设计，你如何
设计。
有没有有顺序的Map实现类，如果有，他们是怎么保证有序的。

hashmap的实现原理，https://blog.csdn.net/mbshqqb/article/details/79799009

下面是自己的总结:

存储结构:
里面存储的是一个entry数组，每个数组元素中的结构是一个entry链表
Entry是map中的一个静态内部类，其中的变量有:key,value,hashcocd,下一个Entry

什么是hash？
又称散列，将任意长度的输入通过散列算法转换成固定长度的输出，该输出就是散列值。这是一种压缩映射，散列值的空间通常远小于输出的空间。不同的输入有可能会散列出相同的输出，因此不能从散列值来确定唯一的输入值。这也是为什么比较两个对象不能仅仅使用hashcode方法比较的原因。

hash碰撞:
对不同的值进行hash运算生成了相同的散列值。这个是不可避免的，但是我们需要尽量的减少其带来的损失。
(1)设计好的hash算法让其尽可能的分布均匀
hashmap中的hash算法解析
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
让key的hashcode本身与它右移16位异或，是为了让它的高位与低位混合，增加低位的随机性，同时也变相保持了高位的特征

计算元素位置的算法:
int index = hash & (arrays.length-1);
那么这也就明白了为什么HashMap的数组长度是2的整数幂。比如以初始长度为16为例，16-1 = 15，15的二进制数位00000000 00000000 00001111。可以看出一个基数二进制最后一位必然位1，当与一个hash值进行与运算时，最后一位可能是0也可能是1。但偶数与一个hash值进行与运算最后一位必然为0，造成有些位置永远映射不上值。

对于null值的处理
hashmap是接受null值的，null值被放在数组的第一个元素当中，取出来的时候怎么处理呢？

hashmap的工作原理？
它的里面有一个Entry数组，在put时我们先根据key值计算出hashcode，进而计算出该元素在数组中的位置，将健值对封装在Map.Entry对象中，然后存储在数组中

若产生hash冲突怎么办？
每个数组元素的位置都是一个链表结构，若计算出来的hashcode相同则将元素追加到该链表当中，这是hashmap的处理方式

在取元素的时候，先计算key值对应的hashcode ，找到元素所在的位置，然后调用key的equals方法去遍历链表，最后找到元素

还有哪些解决hash冲突的方法？
开放寻址法
这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。
再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RH1（key） i=1，2，…，k
当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
链地址法
这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
建立公共溢出区
这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

默认的负载因子0.75
当map的大小超过当前容量的百分之75时会进行自动扩容，会将原来的对象重新放到新的数组中

rehash 的过程是什么样子的？
说白了就是先resize，生成一个新的Entry数组，再transfer将原数组中的值重新计算index放入新的数组中，然后改变阈值为新的长度x负载因子

如果key为null，这始终会被散列到table[0]的桶中，即使是rehash的过程也是一样。非null的key也有可能会被散列到table[0]的位置，例如上图中key=“f”，而且相同的key在在不同的时间可能会被散列到不同的位置，这与rehash有关。

这个过程中容易发生什么问题呢？
容易产生条件竞争，如果在扩容的过程中put数据，会造成意想不到的结果。或者如果两个线程都触发了扩容，也会存在问题

这块有没有遇到过什么比较好的例子？

jdk1.8以后改成了红黑树，为什么？说一下红黑树的原理？

hashmap与hashtable的区别？
HashTable和HashMap的实现原理几乎一样，差别无非是
HashTable不允许key和value为null
HashTable是线程安全的
但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。

篇幅有限，未完待续

❷ 哈稀表是什么东西，HashCode是什么

哈希表是一些键值对的组合，如
Hashtable hs = new Hashtable();
hs.Add('1',200);
hs.Add('2',300);
hs.Add('3',400);
他的键是不能重复的。
我们通过它的键就可以得到他的值，如像，我们要得到300.
只需hs['2']就可以得到300

❸ 什么hash code

是一种编码方式，在Java中，每个对象都会有一个hashcode，Java可以通过这个hashcode来识别一个对象。至于hashcode的具体编码方式，比较复杂（事实上这个编码是可以由程序员重载的），可以参考数据结构书籍。而hashtable等结构，就是通过这个哈希实现快速查找键对象。这是他们的内部联系，但一般编程时无需了解这些，只要知道hashtable实现了一种无顺序的元素排列就可以了。

❹ 程序员必须掌握哪些算法

一.基本算法:

枚举. (poj1753,poj2965)

贪心(poj1328,poj2109,poj2586)

递归和分治法.

递推.

构造法.(poj3295)

模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996)

二.图算法:

图的深度优先遍历和广度优先遍历.

最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra)
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240)
最小生成树算法(prim,kruskal)
(poj1789,poj2485,poj1258,poj3026)
拓扑排序 (poj1094)

二分图的最大匹配 (匈牙利算法) (poj3041,poj3020)

最大流的增广路算法(KM算法). (poj1459,poj3436)

三.数据结构.

串 (poj1035,poj3080,poj1936)

排序(快排、归并排(与逆序数有关)、堆排) (poj2388,poj2299)

简单并查集的应用.

哈希表和二分查找等高效查找法(数的Hash,串的Hash)
(poj3349,poj3274,POJ2151,poj1840,poj2002,poj2503)
哈夫曼树(poj3253)

堆

trie树(静态建树、动态建树) (poj2513)

四.简单搜索

深度优先搜索 (poj2488,poj3083,poj3009,poj1321,poj2251)

广度优先搜索(poj3278,poj1426,poj3126,poj3087.poj3414)

简单搜索技巧和剪枝(poj2531,poj1416,poj2676,1129)

五.动态规划

背包问题. (poj1837,poj1276)

型如下表的简单DP(可参考lrj的书 page149):
E[j]=opt{D+w(i,j)} (poj3267,poj1836,poj1260,poj2533)
E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列) (poj3176,poj1080,poj1159)
C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)
六.数学

组合数学:
1.加法原理和乘法原理.
2.排列组合.
3.递推关系.
(POJ3252,poj1850,poj1019,poj1942)
数论.
1.素数与整除问题
2.进制位.
3.同余模运算.
(poj2635, poj3292,poj1845,poj2115)
计算方法.
1.二分法求解单调函数相关知识.(poj3273,poj3258,poj1905,poj3122)
七.计算几何学.

几何公式.

叉积和点积的运用(如线段相交的判定,点到线段的距离等). (poj2031,poj1039)

多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交)
(poj1408,poj1584)
凸包. (poj2187,poj1113)

中级（校赛压轴及省赛中等难度）:
一.基本算法:

C++的标准模版库的应用. (poj3096,poj3007)

较为复杂的模拟题的训练(poj3393,poj1472,poj3371,poj1027,poj2706)

二.图算法:

差分约束系统的建立和求解. (poj1201,poj2983)

最小费用最大流(poj2516,poj2516,poj2195)

双连通分量(poj2942)

强连通分支及其缩点.(poj2186)

图的割边和割点(poj3352)

最小割模型、网络流规约(poj3308)

三.数据结构.

线段树. (poj2528,poj2828,poj2777,poj2886,poj2750)

静态二叉检索树. (poj2482,poj2352)

树状树组(poj1195,poj3321)

RMQ. (poj3264,poj3368)

并查集的高级应用. (poj1703,2492)

KMP算法. (poj1961,poj2406)

四.搜索

最优化剪枝和可行性剪枝

搜索的技巧和优化 (poj3411,poj1724)

记忆化搜索(poj3373,poj1691)

五.动态规划

较为复杂的动态规划(如动态规划解特别的旅行商TSP问题等)
(poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034)
记录状态的动态规划. (POJ3254,poj2411,poj1185)

树型动态规划(poj2057,poj1947,poj2486,poj3140)

六.数学

组合数学:
1.容斥原理.
2.抽屉原理.
3.置换群与Polya定理(poj1286,poj2409,poj3270,poj1026).
4.递推关系和母函数.
数学.
1.高斯消元法(poj2947,poj1487, poj2065,poj1166,poj1222)
2.概率问题. (poj3071,poj3440)
3.GCD、扩展的欧几里德(中国剩余定理) (poj3101)
计算方法.
1.0/1分数规划. (poj2976)
2.三分法求解单峰(单谷)的极值.
3.矩阵法(poj3150,poj3422,poj3070)
4.迭代逼近(poj3301)
随机化算法(poj3318,poj2454)
杂题(poj1870,poj3296,poj3286,poj1095)
七.计算几何学.

坐标离散化.

扫描线算法(例如求矩形的面积和周长并,常和线段树或堆一起使用)
(poj1765,poj1177,poj1151,poj3277,poj2280,poj3004)
多边形的内核(半平面交)(poj3130,poj3335)

几何工具的综合应用.(poj1819,poj1066,poj2043,poj3227,poj2165,poj3429)

高级（regional中等难度）:
一.基本算法要求:

代码快速写成,精简但不失风格

(poj2525,poj1684,poj1421,poj1048,poj2050,poj3306)

保证正确性和高效性. poj3434

二.图算法:

度限制最小生成树和第K最短路. (poj1639)

最短路,最小生成树,二分图,最大流问题的相关理论(主要是模型建立和求解)
(poj3155, poj2112,poj1966,poj3281,poj1087,poj2289,poj3216,poj2446
最优比率生成树. (poj2728)

最小树形图(poj3164)

次小生成树.

无向图、有向图的最小环

三.数据结构.

trie图的建立和应用. (poj2778)

LCA和RMQ问题(LCA(最近公共祖先问题) 有离线算法(并查集+dfs) 和 在线算法(RMQ+dfs)).(poj1330)
双端队列和它的应用(维护一个单调的队列,常常在动态规划中起到优化状态转移的目的). (poj2823)
左偏树(可合并堆).

后缀树(非常有用的数据结构,也是赛区考题的热点).(poj3415,poj3294)
四.搜索

较麻烦的搜索题目训练(poj1069,poj3322,poj1475,poj1924,poj2049,poj3426)

广搜的状态优化:利用M进制数存储状态、转化为串用hash表判重、按位压缩存储状态、双向广搜、A*算法. (poj1768,poj1184,poj1872,poj1324,poj2046,poj1482)

深搜的优化:尽量用位运算、一定要加剪枝、函数参数尽可能少、层数不易过大、可以考虑双向搜索或者是轮换搜索、IDA*算法. (poj3131,poj2870,poj2286)

五.动态规划

需要用数据结构优化的动态规划.(poj2754,poj3378,poj3017)
四边形不等式理论.

较难的状态DP(poj3133)

六.数学

组合数学.
1.MoBius反演(poj2888,poj2154)
2.偏序关系理论.
博奕论.
1.极大极小过程(poj3317,poj1085)
2.Nim问题.
七.计算几何学.

半平面求交(poj3384,poj2540)

可视图的建立(poj2966)

点集最小圆覆盖.

对踵点(poj2079)

❺ 哈希表map和table哪个性能高

list支持快速的插入和删除，但是查找费时;
vector支持快速的查找，但是插入费时。
map查找的时间复杂度是对数的，这几乎是最快的，hash也是对数的。
如果我自己写，我也会用二叉检索树，它在大部分情况下可以保证对数复杂度，最坏情况是常数复杂度，而std::map在任何情况下都可以保证对数复杂度，原因是它保证存诸结构是完全二叉检索树，但这会在存诸上牺牲一些时间。
STL 中的 map 内部是平衡二叉树，所以平衡二叉树的性质都具备。查找数据的时间也是对数时间。 vector，在分配内存上一般要比 new 高效的多。
为什么说 hash_map 是对数级的？在不碰撞的情况下，hash_map是所有数据结构中查找最快的，它是常数级的。
如果对问题设计了足够好的hash算法，保证碰撞率很低，hash_map的查找效率无可置疑。
另外，STL的map，它的查找是对数级的，是除hash_map外最高的了，你可以说“也许还有改进余地”，但对于99.9999%的程序员，设计一个比STL map好的map，我执悲观态度。
STL的map有平衡策略（比如红黑树什么的），所以不会退化，不需要考虑数据本身的分布问题。只不过，如果数据本身是排好序的，用vector或heap会明显的快些，因为它们的访问比较简单。

我想没必要怀疑stl::map的查找效率,影响效率最主要的因素是什么?算法,在查找问题上,有什么算法比RB_tree更好吗？至少现在还没有。不否 认你可以通过自己写代码，设计一个符合你需要的BR—TREE，比stl：：map简捷那么一点，但最多也就每次迭代中少一行指令而已，处理十万个数据多 执行十万行指令，这对你重要吗？如果你不是在设计OS像Linux，没人会关注这十万行指令花的时间。
rb-tree的时间花在了插入和删除上，如果你不是对插入和删除效率要求很高，你没有理由不选择基于rb-tree的stl::map。

大多数程序员写不出比std::map更好的map，这是当然的。然而并不是std::map的所有特性都出现在我们的程序中，自己编写的可以更适合自己的程序，的确会比std::map更快一些。

关于hash_map，它与map的实现机制是不一样的，map内部一般用树来实现，其查找操作是O(logN)的，这个没有争议，我就不多说了。
hash_map的查找，内部是通过一个从key到value的运算函数来实现的，这个函数“只接受key作为参数”，也就是说，hash_map的查找 算法与数据量无关，所以认为它是O(1)级的。来这里的应该都是达人，可以参看《数据结构》。当然，事实总不这样完美，再引一段前面我自已说的话，进一步 说明，以免误会：
-----------------------------------------
在不碰撞的情况下，hash_map是所有数据结构中查找最快的，它是常数级的。
------------------------------------------
注意我的前提：“在不碰撞的情况下”，其实换句话说，就是要有足够好的hash函数，它要能使key到value的映射足够均匀，否则，在最坏的情况下，它的计算量就退化到O(N)级，变成和链表一样。
如果说 hash_map 是所有容器中最慢的，也只能说：“最拙劣的hash函数”会使hash_map成为查找最慢的容器。但这样说意义不大，因为，最凑巧的排列能使冒泡排序成为最快的排序算法。
BS: "对于大型容器而言,hash_map能够提供比map快5至10倍的元素查找速度是很常见的,尤其是在查找速度特别重要的地方.另一方面,如果hash_map选择了病态的散列函数,他也可能比map慢得多. "
ANSIC++在1998年之后就没再有重大改变，并且决定不再向C++标准库中做任何重大的变更，正是这个原因，hash table(包括hash_map)并没有被列入标准之中，虽然它理应在C++标准之中占有一席之地。
虽然，现在的大多数编译平台支持hash table，但从可移植性方面考虑，还是不用hash table的好。

hehe俺也来凑凑热闹。
1.有的时候vector可以替代map
比如key是整数，就可以以key的跨度作为长度来定义vector。
数据规模很大的时候，差异是惊人的。当然，空间浪费往往也惊人。
2.hash是很难的东西
没有高效低碰撞的算法，hash_xxx没有意义。
而对不同的类型，数据集，不可能有优良的神仙算法。必须因场合而宜。
俺有的解决方法是GP，可不是饭型，是遗传编程，收效不错。

你的百万级的数据放到vector不大合适。因为vector需要连续的内存空间，显然在初始化这个容器的时候会花费很大的容量。
使用map，你想好了要为其建立一个主键吗？如果没有这样的需求，为什么不考虑deque或者list？
map默认使用的是deque作为容器。其实map不是容器，拿它与容器比较意义不大。因为你可以配置它的底层容器类型。

如果内存不是考虑的问题。用vector比map好。map每插入一个数据，都要排序一次。所以速度反不及先安插所有元素，再进行排序。
用 binary_search对已序区间搜索，如果是随机存取iterator，则是对数复杂度。可见，在不考虑内存问题的情况下，vector比map 好。

如果你需要在数据中间进行插入，list 是最好的选择，vector 的插入效率会让你痛苦得想死。

涉及到查找的话用map比较好，因为map的内部数据结构用rb-tree实现，而用vector你只能用线性查找，效率很低。
stl还提供了 hash容器，理论上查找是飞快~~~。做有序插入的话vector是噩梦，map则保证肯定是按key排序的，list要自己做些事情。

HASH类型的查找肯定快，是映射关系嘛，但是插入和删除却慢，要做移动操作, LIST类型的使链式关系，插入非常快，但是查找却费时，需要遍历~~ , 还是用LIST类型的吧，虽然查找慢点，
先快速排序，然后二分查找，效率也不低

❻ 哈希函数怎么用pascal

暴雪公司有个经典的字符串的hash公式

先提一个简单的问题，假如有一个庞大的字符串数组，然后给你一个单独的字符串，让你从这个数组中查找是否有这个字符串并找到它，你会怎么做？

有一个方法最简单，老老实实从头查到尾，一个一个比较，直到找到为止，我想只要学过程序设计的人都能把这样一个程序作出来，但要是有程序员把这样的程序交给用户，我只能用无语来评价，或许它真的能工作，但...也只能如此了。

最合适的算法自然是使用HashTable（哈希表），先介绍介绍其中的基本知识，所谓Hash，一般是一个整数，通过某种算法，可以把一个字符串"压缩" 成一个整数，这个数称为Hash，当然，无论如何，一个32位整数是无法对应回一个字符串的，但在程序中，两个字符串计算出的Hash值相等的可能非常小，下面看看在MPQ中的Hash算法

unsigned long HashString(char *lpszFileName, unsigned long dwHashType)
{
unsigned char *key = (unsigned char *)lpszFileName;
unsigned long seed1 = 0x7FED7FED, seed2 = 0xEEEEEEEE;
int ch;

while(*key != 0)
{
ch = toupper(*key );

seed1 = cryptTable[(dwHashType < < 8) ch] ^ (seed1 seed2);
seed2 = ch seed1 seed2 (seed2 < < 5) 3;
}
return seed1;
}

Blizzard的这个算法是非常高效的，被称为"One-Way Hash"，举个例子，字符串"unitneutralacritter.grp"通过这个算法得到的结果是0xA26067F3。
是不是把第一个算法改进一下，改成逐个比较字符串的Hash值就可以了呢，答案是，远远不够，要想得到最快的算法，就不能进行逐个的比较，通常是构造一个哈希表(Hash Table)来解决问题，哈希表是一个大数组，这个数组的容量根据程序的要求来定义，例如1024，每一个Hash值通过取模运算 (mod)对应到数组中的一个位置，这样，只要比较这个字符串的哈希值对应的位置又没有被占用，就可以得到最后的结果了，想想这是什么速度？是的，是最快的O(1)，现在仔细看看这个算法吧

int GetHashTablePos(char *lpszString, SOMESTRUCTURE *lpTable, int nTableSize)
{
int nHash = HashString(lpszString), nHashPos = nHash % nTableSize;

if (lpTable[nHashPos].bExists && !strcmp(lpTable[nHashPos].pString, lpszString))
return nHashPos;
else
return -1; //Error value
}

看到此，我想大家都在想一个很严重的问题："假如两个字符串在哈希表中对应的位置相同怎么办？",究竟一个数组容量是有限的，这种可能性很大。解决该问题的方法很多，我首先想到的就是用"链表",感谢大学里学的数据结构教会了这个百试百灵的法宝，我碰到的很多算法都可以转化成链表来解决，只要在哈希表的每个入口挂一个链表，保存所有对应的字符串就OK了。

事情到此似乎有了完美的结局，假如是把问题独自交给我解决，此时我可能就要开始定义数据结构然后写代码了。然而Blizzard的程序员使用的方法则是更精妙的方法。基本原理就是：他们在哈希表中不是用一个哈希值而是用三个哈希值来校验字符串。

中国有句古话"再一再二不能再三再四"，看来Blizzard也深得此话的精髓，假如说两个不同的字符串经过一个哈希算法得到的入口点一致有可能，但用三个不同的哈希算法算出的入口点都一致，那几乎可以肯定是不可能的事了，这个几率是1:18889465931478580854784，大概是10的 22.3次方分之一，对一个游戏程序来说足够安全了。

现在再回到数据结构上，Blizzard使用的哈希表没有使用链表，而采用"顺延"的方式来解决问题，看看这个算法：
int GetHashTablePos(char *lpszString, MPQHASHTABLE *lpTable, int nTableSize)
{
const int HASH_OFFSET = 0, HASH_A = 1, HASH_B = 2;
int nHash = HashString(lpszString, HASH_OFFSET);
int nHashA = HashString(lpszString, HASH_A);
int nHashB = HashString(lpszString, HASH_B);
int nHashStart = nHash % nTableSize, nHashPos = nHashStart;

while (lpTable[nHashPos].bExists)
{
if (lpTable[nHashPos].nHashA == nHashA && lpTable[nHashPos].nHashB == nHashB)
return nHashPos;
else
nHashPos = (nHashPos 1) % nTableSize;

if (nHashPos == nHashStart)
break;
}

return -1; //Error value
}

1. 计算出字符串的三个哈希值（一个用来确定位置，另外两个用来校验)
2. 察看哈希表中的这个位置
3. 哈希表中这个位置为空吗？假如为空，则肯定该字符串不存在，返回
4. 假如存在，则检查其他两个哈希值是否也匹配，假如匹配，则表示找到了该字符串，返回
5. 移到下一个位置，假如已经越界，则表示没有找到，返回
6. 看看是不是又回到了原来的位置，假如是，则返回没找到
7. 回到3

怎么样，很简单的算法吧，但确实是天才的idea, 其实最优秀的算法往往是简单有效的算法。

❼ C# HashTable 明白人光临

c#_hashtable- -

一,哈希表(Hashtable)简述

在.NET Framework中，Hashtable是System.Collections命名空间提供的一个容器，用于处理和表现类似key/value的键值对，其中key通常可用来快速查找，同时key是区分大小写；value用于存储对应于key的值。Hashtable中key/value键值对均为object类型，所以Hashtable可以支持任何类型的key/value键值对.

二,哈希表的简单操作

在哈希表中添加一个key/value键值对：HashtableObject.Add(key,value);
在哈希表中去除某个key/value键值对：HashtableObject.Remove(key);
从哈希表中移除所有元素： HashtableObject.Clear();
判断哈希表是否包含特定键key： HashtableObject.Contains(key);
下面控制台程序将包含以上所有操作：
using System;
using System.Collections; //使用Hashtable时，必须引入这个命名空间
class hashtable
{
public static void Main()
{
Hashtable ht=new Hashtable(); //创建一个Hashtable实例
ht.Add("E","e");//添加key/value键值对
ht.Add("A","a");
ht.Add("C","c");
ht.Add("B","b");

string s=(string)ht["A"];
if(ht.Contains("E")) //判断哈希表是否包含特定键,其返回值为true或false
Console.WriteLine("the E key:exist");
ht.Remove("C");//移除一个key/value键值对
Console.WriteLine(ht["A"]);//此处输出a
ht.Clear();//移除所有元素
Console.WriteLine(ht["A"]); //此处将不会有任何输出
}
}

三,遍历哈希表

遍历哈希表需要用到DictionaryEntry Object，代码如下：
for(DictionaryEntry de in ht) //ht为一个Hashtable实例
{
Console.WriteLine(de.Key);//de.Key对应于key/value键值对key
Console.WriteLine(de.Value);//de.Key对应于key/value键值对value
}

四,对哈希表进行排序

对哈希表进行排序在这里的定义是对key/value键值对中的key按一定规则重新排列，但是实际上这个定义是不能实现的，因为我们无法直接在Hashtable进行对key进行重新排列，如果需要Hashtable提供某种规则的输出，可以采用一种变通的做法：
ArrayList akeys=new ArrayList(ht.Keys); //别忘了导入System.Collections
akeys.Sort(); //按字母顺序进行排序
for(string skey in akeys)
{
Console.Write(skey + ":");
Console.WriteLine(ht[skey]);//排序后输出
}

自己看吧，程序员要学会自学，很容易的

❽ 如何正确实现Java中的hashCode方法

正确实现Java中的hashCode方法：
相等和哈希码

相等是从一般的方面来讲，哈希码更加具有技术性。如果我们在理解方面存在困难,我们可以说,他们通过只是一个实现细节来提高了性能。
大多数的数据结构通过equals方法来判断他们是否包含一个元素，例如：
List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");

这个变量contains结果是true，因为,虽然”b”是不相同的实例(此外,忽略字符串驻留),但是他们是相等的。
通过比较实例的每个元素，然后将比较结果赋值给contains是比较浪费的，虽然整个类的数据结构进行了优化，能够提升性能。
他们通过使用一种快捷的方式(减少潜在的实例相等)进行比较，从而代替通过比较实例所包含的每个元素。而快捷比较仅需要比较下面这些方面：
快捷方式比较即通过比较哈希值，它可以将一个实例用一个整数值来代替。哈希码相同的实例不一定相等，但相等的实例一定具有有相同的哈希值。(或应该有,我们很快就会讨论这个)这些数据结构经常通过这种这种技术来命名,可以通过Hash来识别他们的,其中，HashMap是其中最着名的代表。
它们通常是这样这样运作的
当添加一个元素,它的哈希码是用来计算内部数组的索引(即所谓的桶)
如果是,不相等的元素有相同的哈希码,他们最终在同一个桶上并且捆绑在一起,例如通过添加到列表。
当一个实例来进行contains操作时，它的哈希码将用来计算桶值(索引值)，只有当对应索引值上存在元素时，才会对实例进行比较。
因此equals，hashCode是定义在Object类中。
散列法的思想
如果hashCode作为快捷方式来确定相等，那么只有一件事我们应该关心:相等的对象应该具有相同的哈希码，这也是为什么如果我们重写了equals方法后，我们必须创建一个与之匹配的hashCode实现的原因!
否则相等的对象是可能不会有相同的哈希码的,因为它们将调用的是Object's的默认实现。
HashCode 准则
引用自官方文档
hashCode通用约定:
* 调用运行Java应用程序中的同一对象,hashCode方法必须始终返回相同的整数。这个整数不需要在不同的Java应用程序中保持一致。
* 根据equals(Object)的方法来比较，如果两个对象是相等的,两个对象调用hashCode方法必须产生相同的结果。
* 根据equals(Object)的方法是比较，如果两个对象是不相等的，那么两个对象调用hashCode方法并不一定产生不同的整数的结果。但是,程序员应该意识到给不相等的对象产生不同的整数结果将有可能提高哈希表的性能。
第一点反映出了相等的一致性属性，第二个就是我们上面提出的要求。第三个阐述了一个重要的细节，我们将在稍后讨论。
HashCode实现
下面是非常简单的Person.hashCode的实现
@Override
public int hashCode() {
return Objects.hash(firstName, lastName);
}

person’s是通过多个字段结合来计算哈希码的。都是通过Object的hash函数来计算。
选择字段
但哪些字段是相关的吗?需求将会帮助我们回答这个问题:如果相等的对象必须具有相同的哈希码,那么计算哈希码就不应包括任何不用于相等检查的字段。(否则两个对象只是这些字段不同但是仍然有可能会相等，此时他们这两个对象哈希码却会不相同。)
所以用于哈希组字段应该相等时使用的字段的子集。默认情况下都使用相同的字段,但有一些细节需要考虑。
一致性
首先,有一致性的要求。它应该相当严格。虽然它允许如果一些字段改变对应的哈希码发生变化(对于可变的类是不可避免的)，但是哈希数据结构并不是为这种场景准备的。
正如我们以上所见的哈希码用于确定元素的桶。但如果hash-relevant字段发生了改变,并不会重新计算哈希码、也不会更新内部数组。
这意味着以后通过相等的对象，甚至同一实例进行查询也会失败，数据结构计算当前的哈希码与之前存储实例计算的哈希码并不一致,并是错误的桶。
结论:最好不要使用可变字段计算哈希码!
性能
哈希码最终计算的频率与可能调用equals差不多，那么这里将是影响性能的关键部分，因此考虑此部分性能也是非常有意义的。并且与equals相比，优化之后又更大的上升空间。
除非使用非常复杂的算法或者涉及非常多的字段，那么计算哈希码的运算成本是微不足道的、同样也是不可避免的。但是也应该考虑是否需要包含所有的字段来进行运算。集合需要特别警惕的对待。以Lists和sets为例，将会包含集合里面的每一个元素来计算哈希码。是否需要调用它们需要具体情况具体分析。
如果性能是至关重要的，使用Objects.hash因为需要为varargs创建一个数组也许并不是最好的选择。但一般规则优化是适用的:不要过早地使用一个通用的散列码算法,也许需要放弃集合,只有优化分析显示潜在的改进。
碰撞
总是关注性能,这个实现怎么呢?
@Override
public int hashCode() {
return 0;
}

快是肯定的。相等的对象将具有相同的哈希码。并且,没有可变的字段!
但是，我们之前说过的桶呢？！这种方式下所有的实例将会有相同的桶！这将会导致一个链表来包含所有的元素，这样一来将会有非常差的性能。每次调用contains将会触发对整个list线性扫描。
我们希望尽可能少的元素在同一个桶!一个算法返回变化多端的哈希码,即使对于非常相似的对象,是一个好的开始。
怎样才能达到上面的效果部分取决于选取的字段，我们在计算中包含更多的细节，越有可能获取到不同的哈希码。注意：这个与我们所说的性能是完全相反的。因此，有趣的是，使用过多或者过少的字段都会导致糟糕的性能。
防止碰撞的另一部分是使用实际计算散列的算法。
计算Hsah
最简单的方法来计算一个字段的哈希码是通过直接调用hashCode，结合的话会自动完成。常见的算法是首先在以任意数量的数值(通常是基本数据类型)反复进行相乘操作再与字段哈希码相加
int prime = 31;
int result = 1;
result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
return result;

这可能导致溢出,但是不是特别有问题的,因为他们并没有产生Java异常。
注意,即使是非常良好的的哈希算法也可能因为输入特定的模式的数据有导致频繁碰撞。作为一个简单的例子假设我们会计算点的散列通过增加他们的x和y坐标。当我们处理f(x) = -x线上的点时，线上的点都满足：x + y == 0，将会有大量的碰撞。
但是:我们可以使用一个通用的算法，只到分析表明并不正确，才需要对哈希算法进行修改。
总结
我们了解到计算哈希码就是压缩相等的一个整数值：相等的对象必须有相同的哈希码，而出于对性能的考虑：最好是尽可能少的不相等的对象共享相同的哈希码。
这就意味着如果重写了equals方法，那么就必须重写hashCode方法
当实现hashCode
使用与equals中使用的相同的字段(或者equals中使用字段的子集)
最好不要包含可变的字段。
对集合不要考虑调用hashCode
如果没有特殊的输入特定的模式，尽量采用通用的哈希算法
记住hashCode性能,所以除非分析表明必要性，否则不要浪费太多的精力。

❾ Hashtable与HashMap有什么区别

HashTable的应用非常广泛，HashMap是新框架中用来代替HashTable的类，也就是说建议使用HashMap，不要使用HashTable。可能你觉得HashTable很好用，为什么不用呢？这里简单分析他们的区别。

1.HashTable的方法是同步的，HashMap未经同步，所以在多线程场合要手动同步HashMap这个区别就像Vector和ArrayList一样。

2.HashTable不允许null值(key和value都不可以),HashMap允许null值(key和value都可以)。

3.HashTable有一个contains(Object value)，功能和containsValue(Object value)功能一样。

4.HashTable使用Enumeration，HashMap使用Iterator。 以上只是表面的不同，它们的实现也有很大的不同。

5.HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

6.哈希值的使用不同，HashTable直接使用对象的hashCode，代码是这样的：

int hash = key.hashCode();

int index = (hash & 0x7FFFFFFF) % tab.length;

而HashMap重新计算hash值，而且用与代替求模：

int hash = hash(k);
int i = indexFor(hash, table.length);

static int hash(Object x) {
int h = x.hashCode();
h += ~(h << 9);
h ^= (h >>> 14);
h += (h << 4);
h ^= (h >>> 10);
return h;
} static int indexFor(int h, int length) {
return h & (length-1);
}
以上只是一些比较突出的区别，当然他们的实现上还是有很多不同的，比如HashMap对null的操作。Hashtable和HashMap的区别：
1.Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类；
2.Hashtable中的方法是同步的，而HashMap中的方法在缺省情况下是异步的。即是说，在多线程应用程序中，不用专门的操作就安全地可以使用Hashtable了；而对于HashMap，则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到解决：
Map Collections.synchronizedMap(Map m)
这个方法返回一个同步的Map，这个Map封装了底层的HashMap的所有方法，使得底层的HashMap即使是在多线程的环境中也是安全的。
3.在HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，即可以表示HashMap中没有该键，也可以表示该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键，而应该用containsKey()方法来判断。Hashtable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现

HashMap允许将null作为一个entry的key或者value，而Hashtable不允许

还有就是，HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。因为contains方法容易让人引起误解。最大的不同是，Hashtable的方法是Synchronize的，而HashMap不是，在
多个线程访问Hashtable时，不需要自己为它的方法实现同步，而HashMap
就必须为之提供外同步。

❿ 什么是哈希算法

就是空间映射函数，例如，全体的长整数的取值作为一个取值空间，映射到全部的字节整数的取值的空间，这个映射函数就是HASH函数。通常这种映射函数是从一个非常大的取值空间映射到一个非常小的取值空间，由于不是一对一的映射，HASH函数转换后不可逆，即不可能通过逆操作和HASH值还原出原始的值，受到计算能力限制（注意，不是逻辑上不可能，前面的不可能是逻辑上的）而且也无法还原出所有可能的全部原始值。HASH函数运用在字典表等需要快速查找的数据结构中，他的计算复杂度几乎是O(1)，不会随着数据量增加而增加。另外一种用途就是文件签名，文件内容很多，将文件内容通过HASH函数处理后得到一个HASH值，验证这个文件是否被修改过，只需要把文件内容用同样的HASH函数处理后得到HASH值再比对和文件一起传送的HASH值即可，如不公开HASH算法，那么信道是无法篡改文件内容的时候篡改文件HASH值，一般应用的时候，HASH算法是公开的，这时候会用一个非对称加密算法加密一下这个HASH值，这样即便能够计算HASH值，但没有加密密钥依然无法篡改加密后HASH值。这种算法用途很广泛，用在电子签名中。HASH算法也可进行破解，这种破解不是传统意义上的解密，而是按照已有的HASH值构造出能够计算出相同HASH值的其他原文，从而妨碍原文的不可篡改性的验证，俗称找碰撞。这种碰撞对现有的电子签名危害并不严重，主要是要能够构造出有意义的原文才有价值，否则就是构造了一个完全不可识别的原文罢了，接收系统要么无法处理报错，要么人工处理的时候发现完全不可读。理论上我们终于找到了在可计算时间内发现碰撞的算法，推算了HASH算法的逆操作的时间复杂度大概的范围。HASH算法的另外一个很广泛的用途，就是很多程序员都会使用的在数据库中保存用户密码的算法，通常不会直接保存用户密码（这样DBA就能看到用户密码啦，好危险啊），而是保存密码的HASH值，验证的时候，用相同的HASH函数计算用户输入的密码得到计算HASH值然后比对数据库中存储的HASH值是否一致，从而完成验证。由于用户的密码的一样的可能性是很高的，防止DBA猜测用户密码，我们还会用一种俗称“撒盐”的过程，就是计算密码的HASH值之前，把密码和另外一个会比较发散的数据拼接，通常我们会用用户创建时间的毫秒部分。这样计算的HASH值不大会都是一样的，会很发散。最后，作为一个老程序员，我会把用户的HASH值保存好，然后把我自己密码的HASH值保存到数据库里面，然后用我自己的密码和其他用户的用户名去登录，然后再改回来解决我看不到用户密码而又要“偷窥”用户的需要。最大的好处是，数据库泄露后，得到用户数据库的黑客看着一大堆HASH值会翻白眼。