哈希算法以及哈希表（Hash table，也叫散列表）_哈希表和哈希算法

首先来了解一下基本概念

通俗来说：
数组和向量都可以存储对象，但对象的存储位置是随机的，也就是说对象本身与其存储位置之间没有必然的联系。当要查找一个对象时，只能以某种顺序（如顺序查找或二分查找）与各个元素进行比较，当数组或向量中的元素数量很多时，查找的效率会明显的降低。

也即是说这是一种有效的存储方式，是不与其他元素进行比较，一次存取，便能得到所需要的记录。这就需要在对象的存储位置和对象的关键属性（设为 key）之间建立一个特定的对应关系（设为 f），使每个对象与一个唯一的存储位置相对应。在查找时，只要根据待查对象的关键属性 key 计算f(key)的值即可。如果此对象在集合中，则必定在存储位置 f(key)上，因此不需要与集合中的其他元素进行比较。称这种对应关系 f 为哈希（hash）方法，按照这种思想建立的表为哈希表。

• 哈希算法，是一类算法；
• 哈希表（Hash Table）是一种数据结构；
• 哈希函数，是支撑哈希表的一类函数；
• Map是映射、地图的意思，在Java中Map表示一种把K映射到V的数据类型；
• HashMap是Java中用哈希数据结构实现的Map；
  一、Hash算法
  1.是什么？
  1）先来看英语翻译：

hash
英 [hæʃ] 美 [hæʃ]
n. 剁碎的食物；混杂，拼凑；重新表述
vt. 搞糟，把…弄乱；切碎；推敲
n. (Hash)人名；(阿拉伯、保、英)哈什；(西)阿什

正式上会被称为“散列 ”。有时候也叫“哈希 ”，据说是因为最早翻译的人以为这是某个叫Hash 的人发明的算法，所以音译了其名字；
（下面我可能会根据情况混合使用这些词，所以要记得他们是同义词）
2）Hash算法 是这样一类算法：这类算法接受任意长度的二进制输入值，对输入值做换算（切碎），最终给出固定长度的二进制输出值；

• 所以注意：
  Hash算法 不是某个固定的算法，它代表的是一类算法。

以更好理解的方式来说，Hash算法 是摘要算法 ：也就是说，从不同的输入中，通过一些计算摘取出来一段输出数据，值可以用以区分输入数据。
MD5 可能是最著名的一种Hash算法了。

2. 有什么用？

1）信息安全领域：
Hash算法 可用作加密算法。
如文件校验：通过对文件摘要，可以得到文件的“数字指纹”，你下载的任何副本的“数字指纹”只要和官方给出的“数字指纹”一致，那么就可以知道这是未经篡改的。例如著名的MD5 ；
2）数据结构领域：
Hash算法 通常还可用作快速查找。
这是今天我想说的部分。根据Hash函数 我们可以实现一种叫做哈希表（Hash Table）的数据结构。这种结构可以实现对数据进行快速的存取。

Java 使用哈希表类（Hashtable）来实现哈希表，以下是与哈希表相关的一些概念：

• 容量（Capacity）：Hashtable 的容量不是固定的，随对象的加入其容量也可以自动增长。
• 关键字（Key）：每个存储的对象都需要有一个关键字，key 可以是对象本身，也可以是对象的一部分（如某个属性）。要求在一个 Hashtable 中的所有关键字都是唯一的。
• 哈希码（Hash Code）：若要将对象存储到 Hashtable 上，就需要将其关键字 key 映射到一个整型数据，成为 key 的哈希码。
• 项（Item）：Hashtable 中的每一项都有两个域，分别是关键字域 key 和值域 value（存储的对象）。Key 和 value 都可以是任意的 Object 类型的对象，但不能为空。
• 装填因子（Load Factor）：装填因子表示为哈希表的装满程度，其值等于元素数比上哈希表的长度。

哈希表的使用

//哈希表类主要有三种形式的构造方法：

Hashtable(); //默认构造函数，初始容量为 101，最大装填因子为 0.75

Hashtable(int capacity);

Hashtable(int capacity,float loadFactor)

1
2
3
4
5
6
7
8

哈希表的创建也可以通过 new 操作符实现。其语句为：

HashTable has=new HashTable();

1
2

哈希表类主要方法：