哈希算法

哈希算法简介

散列算法（Hash Algorithm），又称哈希算法，杂凑算法，是一种从任意文件中创造小的数字「指纹」的方法。与指纹一样，散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。

Hash 算法能将将任意长度的二进制明文映射为较短的二进制串的算法，并且不同的明文很难映射为相同的 Hash 值。

也可以理解为空间映射函数，是从一个非常大的取值空间映射到一个非常小的取值空间，由于不是一对一的映射，Hash 函数转换后不可逆，意思是不可能通过逆操作和 Hash 值还原出原始的值。

散列方法的主要思想是根据结点的关键码值来确定其存储地址：以关键码值K为自变量，通过一定的函数关系h(K)(称为散列函数)，计算出对应的函数值来，把这个值解释为结点的存储地址，将结点存入到此存储单元中。检索时，用同样的方法计算地址，然后到相应的单元里去取要找的结点。通过散列方法可以对结点进行快速检索。散列（hash，也称“哈希”）是一种重要的存储方式，也是一种常见的检索方法。

牛客刷题

1.在哈希法存储中，冲突指的是（ A ）
A.不同关键字值对应到相同的存储地址
B.两个数据元素具有相同序号
C.两个数据元素的关键字值不同，而非关键字值相同
D.数据元素过多
解析：
1.哈希函数：
哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表成为哈希表。
基本思想：首先在元素的关键字K和元素的位置P之间建立一个对应关系f，使得P=f(K),其中f成为哈希函数。
创建哈希表时，把关键字K的元素直接存入地址为f(K)的单元；查找关键字K的元素时利用哈希函数计算出该元素的存储位置P=f(K).
创建哈希表时，把关键字K的元素直接存入地址为f(K)的单元；查找关键字K的元素时利用哈希函数计算出该元素的存储位置P=f(K).
2.哈希冲突：
当关键字集合很大时，关键字值不同的元素可能会映像到哈希表的同一地址上，即K1!=K2，但f(K1)=f(K2),这种现象称为hash冲突，实际中冲突是不可避免的，只能通过改进哈希函数的性能来减少冲突。

2.判断下列说法是否正确：设H(x)是一哈希函数，有K个不同的关键字(X1, X2, …Xk)满足H(x1)=H（x2)…=H(Xk)，若用线性探测法将这K个关键字存入哈希表中，则至少要探测K-1次。（错误）
解析：
当冲突发生时，按照某种方法继续探测基本表中的其他存储单元，直到找到一个空闲位置为止。
一般形式：hi = (h(k)+di)mod m, i = 1,2,3…,k (k<=m-1)
如果di = 1,2,3,…，m-1时称为线性探测。
所以这k个数存入哈希表中至少要探测（1+2+3+…+k-1）= k(k-1)/2

3. HASH 函数冲突处理方式不包括以下哪一项：
A.开放定址法
B.链地址法
C.插入排序法
D.公共溢出区法
HASH 函数冲突处理方式包括：
开放定址法
再哈希法
链地址法
设置公共溢出区法

4. 线程安全的map在JDK 1.5及其更高版本环境有哪几种方法可以实现?
A. Map map = new HashMap()
B. Map map = new TreeMap()
C. Map map = new ConcurrentHashMap();
D. Map map = Collections.synchronizedMap(new HashMap());

HashMap,TreeMap 未进行同步考虑，是线程不安全的。
HashTable 和 ConcurrentHashMap 都是线程安全的。区别在于他们对加》锁的范围不同，HashTable 对整张Hash表进行加锁，而ConcurrentHashMap将Hash表分为16桶(segment)，每次只对需要的桶进行加锁。
Collections 类提供了synchronizedXxx()方法，可以将指定的集合包装成线程同步的集合。比如，
List list = Collections.synchronizedList(new ArrayList());
Set set = Collections.synchronizedSet(new HashSet());