哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　如果我们可以按这样一种方式在我们的列表中分配记录，情况就会好一些，即每个列表约有相同条目的记录，而不管键值 中数字的分布。我们需要一种方法能够把客户号码混合到一起并更好地分布结果。例如，我们可以取号码中的每位数，乘以某 个大的数（随着数字位置的不同而不同），然后将结果相加产生一个总数，把这个数除以 10，并将余数作为列表索引值（index）。 当读入记录时，程序在客户号码上运行这个哈希（hash) 函数来确定记录属于哪个列表。当用户需要查询时，将同一个哈希函 数作为一个“key”用于客户号码，这样就可以搜索正确的列表了。 像这样的一个数据结构就称为一个哈希表（hashtable)。

　　我们可以看到在 hashmap 中要找到某个元素，需要根据 key 的 hash 值来求得对应数组中的位置。如何计算这个位置就 是 hash 算法。前面说过 hashmap 的数据结构是数组和链表的结合，所以我们当然希望这个 hashmap 里面的元素位置尽量的 分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用 hash 算法求得这个位置的时候，马上就可以知道对应 位置的元素就是我们要的，而不用再去遍历链表。

　　设想一下，你有一个包含约一千条记录的数据文件。比如一个小企业的客户记录还有一个程序，它把记录读到内存中进行 处理。每个记录包含一个唯一的五位数的客户 ID 号、客户名字、地址、帐户结余等等。假设记录不是按客户 ID 号顺序分类的， 所以，如果程序要将客户号作为“key” 来查找一个特殊的客户记录，唯一的查找方法就是连续地搜索每个记录。有时侯，它会 很快找到你需要的记录；但有时侯，在程序找到你需要的记录前，它几乎已搜索到了最后一条记录。如果要在 1,000 条记录中 搜索，那么查找任何一条记录都需要程序平均查核 500.5 ((1000 1 )/2)条记录。如果你常需要查找数据，你应该需要一 个更快的方法来找到一条记录。

　　当我们往 hashmap 中 put 元素的时候，先根据 key 的 hash 值得到这个元素在数组中的位置（即下标），然后就可以把 这个元素放到对应的位置中了。如果这个元素所在的位子上已经存放有其他元素了，那么在同一个位子上的元素将以链表的形 式存放，新加入的放在链头，最先加入的放在链尾。从 hashmap 中 get 元素时，首先计算 key 的 hashcode，找到数组中对 应位置的某一元素，然后通过 key 的 equals 方法在对应位置的链表中找到需要的元素。只要满足这两个基本的要求，key 和 value 可以是任何对象。注意，因为 key 和 value 必须是对象，所以原始类型（primitive types）必须通过运用诸如 Integer(int)的方法转换成对象。从这里我们可以想象得到，如果每个位置上的链表只有一个元素，那么 hashmap 的 get 效率将是最高的，但是理想总是美好的，现实总是有困难需要我们去克服，哈哈~

　　例如 User 这种对象，为了保证两个具有相同属性的 user 的 hashcode 相同，我们就需要改写 hashcode 方法，比方把 hashcode 值的计算与 User 对象的 id 关联起来，那么只要 user 对象拥有相同 id，那么他们的 hashcode 也能保持一致了， 这样就可以找到在 hashmap 数组中的位置了。如果这个位置上有多个元素，还需要用 key 的 equals 方法在对应位置的链表 中找到需要的元素，所以只改写了 hashcode 方法是不够的，equals 方法也是需要改写滴~当然啦，按正常思维逻辑，equals 方法一般都会根据实际的业务内容来定义，例如根据 user 对象的 id 来判断两个 user 是否相等,还可以根据名称、年龄和性 别来判定两个 user 是否相等。

　　hashCode 方法的定义用到了 native 关键字，表示它是由 C 或 C采用较为底层的方式来实现的，你可以认为它返回了 该对象的内存地址；equals()方法把它的对象同另一个对象进行比较，如果这两个对象代表相同的信息，则返回 true。该方 法也查看并确保这两个对象属于相同的类。如果两个参照对象是完全一样的对象，则 Object.equals()返回 true，这就说 明了为什么这个方法通常不是很适合的原因。在大多数情况下，你需要一个方法来一个字段一个字段地进行比较，因为我们认 为代表相同数据的不同对象是相等的。

　　一种加快搜索的方法就是把记录分成几段，这样，你就不用搜索一个很大的列表了，而是搜索几个短的列表。对于我们数 字式的客户 ID 号，你可以建 10 个列表。以 0 开头的 ID 号组成一个列表，以 1 开头的 ID 号组成一个列表，依此类推。那么 要查找客户 ID 号 38016，你只需要搜索以 3 开头的列表就行了。如果有 1,000 条记录，每个列表的平均长度为 100（1,000 条记录被分成 10 个列表），那么搜索一条记录的平均比较次数就降到了约 50（见图 1）。

　　看下图，左边两组是数组长度为 16（2 的 4 次方），右边两组是数组长度为 15。两组的 hashcode 均为 8 和 9，但是很 明显，当它们和 1110“与”的时候，产生了相同的结果，也就是说它们会定位到数组中的同一个位置上去，这就产生了碰撞，8 和 9 会被放到同一个链表上，那么查询的时候就需要遍历这个链表，得到 8 或者 9，这样就降低了查询的效率。同时，我们也 可以发现，当数组长度为 15 的时候，hashcode 的值会与 14（1110）进行“与”，那么最后一位永远是 0，而 0001，0011， 0101，1001，1011，0111，1101 这几个位置永远都不能存放元素了，空间浪费相当大，更糟的是这种情况中，数组可以使 用的位置比数组长度小了很多，这意味着进一步增加了碰撞的几率，减慢了查询的效率！