散列表的实现常常叫做散列。散列是一种用以常数平均时间执行插入，删除，和查找的技术。但是那些需要元素信息排序的树操作不会得到支持。因此例如findMax,findMin以及排序后遍历这些操作都是散列不支持的。
如果当一个元素被插入时与已经插入的元素散列（比如散列表的数组序号，很多元素插入到同一个数组序号中），那么就会产生一个冲突，这个冲突需要消除。解决冲突的办法有两种：
1 分离链接法
2 开放定址法（包括线性探测，平方探测，，双散列）
两者都有可能需要再散列
下面说明分离链接法，上代码：
package com.itany.separatechainning;import java.util.LinkedList;import java.util.List;/* *解决冲突的第一个方法时分离链接法 其做法是将散列到同一个值得所有元素保留到一个表中 *为执行一次查找 我们通过散列函数来决定究竟遍历哪一个链表，然后我们再在被确定的链表中执行一次查找 *散列表存储一个List链表数组 */public class SeparateChainingHashTable<T>{private static final int DEFAULT_TABLE_SIZE=101;//我们定义散列表的填装因子：散列表中元素个数和散列表大小的比 这里是1 即集合链表的平均长度是1private int currentSize;private List<T>[] theLists;public SeparateChainingHashTable(){this(DEFAULT_TABLE_SIZE);}public SeparateChainingHashTable(int size){//对数组中的List进行初始化theLists=new LinkedList[nextPrime(size)];for(int i=0;i<theLists.length;i++){theLists[i]=new LinkedList<T>();}}public void makeEmpty(){for (List<T> list : theLists){list.clear();}currentSize=0;}public void insert(T t){List<T> whichList=theLists[myHash(t)];if(!contains(t)){whichList.add(t);currentSize++;if(currentSize>theLists.length)reHash();}}public boolean contains(T t){//通过myHash找出是哪一个集合List<T> whichList=theLists[myHash(t)];return whichList.contains(t);}public void remove(T t){List<T> whichList=theLists[myHash(t)];if(contains(t)){whichList.remove(t);currentSize–;}}private int myHash(T t){int hash=t.hashCode();//对每一个t得到数组的序号 大小从0-theLists.length-1 进行分配hash%=theLists.length;//防止hash值为负数if(hash<0)hash+=theLists.length;return hash;}//有一种情况是currentSize>theLists.length 需要对数组进行扩容 即再散列//因为列表装的太满 那么操作时间将会变得更长，且插入操作可能失败 此时的方法时新建另外一个两倍大的表//而且使用一个新的相关的散列函数(因为计算时tableSize变了)，扫描整个原始散列表，计算每一个元素的新散列值 并将它们插入到新表中private void reHash(){List<T>[] oldLists=theLists;//复制一下一会要用 theLists在重新new一个theLists=new LinkedList[nextPrime(2*theLists.length)];for(int i=0;i<theLists.length;i++){theLists[i]=new LinkedList<T>();}//把原来的元素复制到新的数组中 注意是把集合中的元素复制进去for(int i=0;i<oldLists.length;i++){for (T t : oldLists[i]){insert(t);}}}//表的大小是一个素数 这可以保证一个很好的分布//是否是素数private static boolean isPrime(int num){int i=1;while((num%(i+1))!=0){i++;}if(i==num-1){return true;}else{return false;}}private static int nextPrime(int num){while(!isPrime(num)){num++;}return num;}}package com.itany.separatechainning;//可以放在散列表中的Employee类的例子/* * 想把类放在散列表中 必须提供两个方法，一个是equals方法 因为要在list的集合中进行查找contains方法时会用到equals进行比较 * 还有一个是hashCode方法 因为需要通过它来找出Employee对象该放在哪一个集合中（找出数组的对应序号） */public class Employee{private String name;public Employee(String name){this.name=name;}@Overridepublic boolean equals(Object obj){return obj instanceof Employee && name.equals(((Employee)obj).name);}public int hashCode(){//String类是有自己的hashCode方法return name.hashCode();}/** String类自己的hashCode方法* public int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];}hash = h;}return h;}*/}package com.itany.separatechainning;public class Test{public static void main(String[] args){Employee e1=new Employee("zhangsan");Employee e2=new Employee("lisi");Employee e3=new Employee("wangwu");Employee e4=new Employee("zhaoliu");SeparateChainingHashTable<Employee> sc=new SeparateChainingHashTable<Employee>();System.out.println(sc.contains(e1));sc.insert(e1);System.out.println(sc.contains(e1));sc.remove(e1);System.out.println(sc.contains(e1));}}结果：
falsetruefalse
要克服生活的焦虑和沮丧，得先学会做自己的主人
