本文共 2627 字，大约阅读时间需要 8 分钟。
数据结构(哈希表Hash)
1.基础
定义：根据关键码(Key)去寻找值(Value)的数据映射。
查询步骤：1. 用散列函数将被查找的键转换为数组的一个索引。2. 再解决碰撞冲突(collision)2.散列方法
整数：除留余数法(modular hashing)，选择大小为素数M(使用素数散列值的分布会更好)的数组，对于任意正整数k，计算k除以M的余数。
浮点数：将键表示为二进制数然后再使用除留余数法(Java使用的方法) 字符串：//字符串的散列函数int hash = 0;for (int i = 0; i < s.length; i++){ hash = (R * hash + s.charAt(i)) % M //charAt()能返回一个char值，即一个16位整数} 组合键：如果键的类型含有多个整型变量，我们可以和String类型一样将他们混合起来。例如查询Date int hash = (((day * R + month) % M) * R + year) % M
public class Transaction{ private final String who; private final Date when; private final double amount; public int hashCode(){ int hash = 17; hash = 31 * hash + who.hashCode(); hash = 31 * hash + when.hashCode(); hash = 31 * hash + ((Double) amount).hashCode(); return hash; }} 注意：每一种数据的hashCode()必须和equals()一致。需注意，如果两个对象的hashCode()的返回值相同，这两个对象也有可能不同，还需要用equals()进行判断。所以在为自定义的数据类型定义散列函数时，需同时重写hashCode()和equals()
软缓存：如果散列值的计算很耗时，那么可以将每个键的散列值缓存起来。即第一次调用hashCode()时计算对象的散列值，并使用一个hash变量保存其值，之后对hashCode()的调用直接返回hash变量的值。Java的String对象就使用了这种方法来减少计算量
总结：要为一个数据类型实现一个优秀的散列方法需要满足：1. 一致性(等价的键必然产生相等的散列值) 2.高效性(计算简便) 3.均匀性(均匀的散列所有值)
3.解决碰撞的方法
拉链法(separate chaining)：将大小为M的数组中的每个元素指向一条链表，链表中的每个结点都存储了散列值为该元素的索引的键值对。
基本思想：选择足够大的M，使得所有链表都尽可能短以保证高效的查找。 删除操作：先用散列值找到含有该键的对象，然后调用该对象的delete()方法
开放地址散列表(open-addressing)：用大小为M的数组保存N个键值对(M>N)，即依靠数组中的空位解决碰撞冲突。其中线性探测法为最简单的开放地址散列表 基本思想：与其将内存用作链表，不如将他们用做散列表的空元素 线性探测法(linear probing)：当发生碰撞时，我们直接检查散列表中的下一个位置。这样线性探测可能产生三种结果：命中(键相同)、未命中(没有键)、继续查找(键不同)。
步骤：用散列函数找到键在数组中的索引，检查其中的键和被查找的键是否相同。如果不同则继续查找(将索引增大，到达数组结尾时折回数组的开头)，直到找到该键或者遇到一个空元素 键蔟：元素在插入数组后聚集成的一组连续条目 删除操作：将蔟中被删除键的右侧所有键重新插入散列表。不能直接将该键所在的位置设为null，这会使得在此位置之后的元素无法被查找。
4.分析
性能分析：在没有冲突的情况下查找时间复杂度仅为O(1)。平均性能依赖于冲突的处理方式和散列表的使用率(填装因子) α \alpha α,
使用场景：对查找性能要求高，数据元素之间无逻辑关系要求的情况
HashMap基于哈希表实现，其内部通过单链表解决冲突问题。HashMap是非线程安全的，一般用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap(Java 5以上)。
HashMap存数据过程： HashMap内部维护了一个存储数据的Entry数组，每一个Entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexFor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7FFFFFFF屏蔽符号位后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头。
HashMap中key和value都允许为null。key为null的键值对永远都放在以table[0]为头结点的链表中。
HashSet：
- 基于HashMap实现，内部是大量借用HashMap的实现，其本身是调用HashMap的一个代理
- Map存储键值对，而Set只储存对象
API
| 函数名 | 描述 | 函数名 | 描述 |
|---|---|---|---|
| size() | Map大小 | isEmpty() | Map是否为空 |
| get(key) | 返回key对应的value | containsKey(key) | Map中是否包含key |
| put(key, value) | 把键值对放入Map中 | putAll(map) | 复制map中的所有键值对到Map中 |
| remove(key) | 将key移出Map | clear() | 将Map清空 |
| containsValue(value) | 是否含有value | keySet() | 返回一个包含所有key的Set |
| values() | 返回一个包含所有value的Collection | clone() | 返回一个Map的浅拷贝 |
转载地址：http://yfqvb.baihongyu.com/