散列表是一种空间换时间的数据结构，在算法中提升效率的一种常用的方法。但是，正如其特点，有时候所消耗的空间，真让人头疼，用的时候在二者之间权衡。
散列表，又叫哈希表（HashTable），是能够通过给定的关键字的值直接访问到具体对应值的数据结构。也就是说，把关键字映到一个表中的位置来直接访问记录，以加快访问速度。
通常，我们通过Key来找Value，也就是说，通过Key访问一个映射表来得到Value的地址。而这个映射表，也叫作散列函数或者哈希函数，存放记录的数组叫做散列表。
如果可以通过不同的Key访问到同一个Value，那么就发生了碰撞，我们需要的是通过一个Key可以访问到唯一的Value。
常用的处理冲突的方法有：
开放地址法（开放寻址法）
就是当这个key通过哈希函数找到存放value地址的位置，当这个位置已经存放数据，就存在其紧跟着后面没有占用的位置，如果超过了最大长度，对最大长度取余，这里移动的地址是产生冲突的偏移量。
再哈希法
产生冲突后，用关键字其他部分继续计算地址，直到不产生冲突，当这种方法增加了时间。
链地址法
当产生冲突，把处于同一地址的数据做成一个链表，这种方法最常见。
建立公共溢出区
建立一个公共溢出区，把产生冲突的新地址放在这个公共溢出区里。
访问速度快
由于散列表有散列函数，把Key映射到一个地址上，访问key对映的Value时候，不需要查找，直接跳到那个地址，因此，散列表的增删改查等任何操作，速度都比较快。
需要额外的空间
当发生冲突，需要额外的空间去存储，空间换时间，有舍才有得。
无序
为了快速找到访问的元素，根据散列函数直接找到存储地址，访问速度就快起来，但是有序访问没有办法实现。
可能产生碰撞
没有完美的散列函数，无论如何总会产生冲突，采用冲突的处理办法，就会使散列表变得更加复杂。
下面展示如何实现一个散列表，这里用数组代替散列表元素（在在真实情况下，大多数语言的实现中，大多数元素都是一个特别的数组，每个元素对应一个地址），每个数组元素作为一个地址。
public class Entry { int key; int value; Entry next; public Entry(int key, int value, Entry next) { super(); this.key = key; this.value = value; this.next = next; } } public class HashTable { /** * 默认散列表的初始长度 * 设置小一点，这样扩容的时候看的清楚 * 在实际使用中其实可以在初始化传参数，因为扩容是很消耗性能的 */ private static final int DEFAULT_INITIAL_CAPACITY = 4; /** * 扩容因子 */ private static final float LOAD_FACTOR = 0.75f; /** * 散列表数组 */ private Entry[] table = new Entry[DEFAULT_INITIAL_CAPACITY]; private int size = 0; private int use = 0; public void put(int key, int value) { int index = hash(key); if (table[index] == null) { table[index] = new Entry(-1, -1, null); } Entry e = table[index]; if (e.next == null) { //不存在的值，向链表中添加，有可能扩容，要用table属性 table[index].next = new Entry(key, value, null); size++; use++; //不存在的值，说明是个未用过的地址，需要判断是否扩容 if (use >= table.length * LOAD_FACTOR) { resize(); } }else { //本身存在的值，修改已有的值 for (e = e.next; e != null; e =e.next) { int k = e.key; if (k == key) { e.value = value; return; } } //不存在相同的值，直接向链表中添加元素 Entry temp = table[index].next; Entry newEntry = new Entry(key, value, temp); table[index].next = newEntry; size ++; } } /** * 删除 * @param key */ public void remove( int key) { int index = hash(key); Entry e = table[index]; Entry pre = table[index]; if (e != null && e.next !=null) { for(e = e.next ; e != null; pre = e, e = e.next){ int k = e.key; if (k == key) { pre.next = e.next; size --; return; } } } } /** * 获取 */ public int get(int key) { int index = hash(key); Entry e = table[index]; if (e != null && e.next != null) { for (int i = 0; i < table.length; i++) { for (e = e.next; e != null; e =e.next) { int k = e.key; if (k == key) { return e.value; } } } } return -1; } /** * 获取散列表中元素的个数 */ public int size() { return size; } /** * 本身散列表是不该有这个方法的，在这里只是为了清楚地看到确实扩容了。 * @return */ public int getLength() { return table.length; } /** * 根据key，通过哈希函数获取位于散列表数组中的哪个位置 * @param key * @return */ public int hash(int key) { return key % table.length; } /** * 扩容 */ public void resize() { int newLength = table.length * 2; Entry[] oldTable = table; table = new Entry[newLength]; use =0; for (int i = 0; i < oldTable.length; i++) { if (oldTable[i] != null && oldTable[i].next != null) { Entry entry = oldTable[i]; while (null != entry.next) { Entry next = entry.next; //重新计算哈希值，放入新的地址 int index = hash(next.key); if (table[index] == null) { use ++; table[index] = new Entry(-1, -1, null); } table[index].next = new Entry(next.key, next.value, table[index].next); //可以用下面三行代替 // Entry temp = table[index].next; // Entry newEntry = new Entry(next.key, next.value, temp); // table[index].next = newEntry; entry = next; } } } } } public class HashTableTest { public static void main(String[] args) { HashTable hashTable = new HashTable(); hashTable.put(1, 10); hashTable.put(2, 20); hashTable.put(5, 50);//和key为1的元素落在一个散列地址上了，实际使用长度为2 System.out.println(hashTable.getLength());//散列表长度为4 hashTable.put(3, 30);//总长度为4，加上该元素后长度就 大于等于3 了，所以扩容 System.out.println(hashTable.getLength());//散列表长为8 //在扩容后4个元素又分别落在不同的地址上 hashTable.put(6, 60);//使用第5 个地址 hashTable.put(7, 70);//使用第6个地址，为8的0.75倍，又需要扩容 System.out.println(hashTable.getLength());//散列表长度为16 System.out.println(hashTable.get(1));//10 System.out.println(hashTable.get(3));//30 System.out.println(hashTable.get(5));//50 System.out.println(hashTable.get(6));//60 } }