0001 /* 0002 * 基于散列表实现的映射结构 0003 * 采用分离链策略解决冲突 0004 */ 0005 0006 package dsa; 0007 0008 public class Map_HashTable implements Map { 0009 private Map[] A;//桶数组,每个桶本身也是一个(基于列表实现的)映射结构 0010 private int N;//散列表长 0011 private final double maxLemda = 0.75;//装填因子上限 0012 private int size;//映射结构的规模 0013 private EqualityTester T;//判等器 0014 0015 //默认构造方法 0016 public Map_HashTable() 0017 { this(0, new EqualityTesterDefault()); } 0018 0019 //构造方法 0020 public Map_HashTable(int n, EqualityTester t) { 0021 T = t; 0022 N = p(n);//桶数组容量取为不小于n的最小素数 0023 A = new Map[N]; 0024 for (int i = 0; i < N; i++) A[i] = new Map_DLNode(T); 0025 size = 0; 0026 } 0027 0028 /***************************** 辅助方法 *****************************/ 0029 //散列定址函数(采用模余法) 0030 private int h(Object key) 0031 { return key.hashCode() % N; } 0032 0033 //判断n是否为素数 0034 private static boolean prime(int n) { 0035 for (int i = 3; i < 1 + Math.sqrt(n); i++) 0036 if (n / i* i == n) return false; 0037 return true; 0038 } 0039 0040 //取不小于n的最小素数 0041 private static int p(int n) { 0042 if (3 > n) n = 3; 0043 n = n | 1;//奇数化 0044 while (!prime(n)) n += 2; 0045 return n; 0046 } 0047 0048 /***************************** ADT方法 *****************************/ 0049 //查询映射结构当前的规模 0050 public int getSize() 0051 { return size; } 0052 0053 //判断映射结构是否为空 0054 public boolean isEmpty() 0055 { return 0 == size; } 0056 0057 //若M中存在以key为关键码的条目,则返回该条目的数据对象;否则,返回null 0058 public Object get(Object key) 0059 { return A[h(key)].get(key); } 0060 0061 //若M中不存在以key为关键码的条目,则将条目(key, value)加入到M中并返回null 0062 //否则,将已有条目的数据对象替换为value,并返回原先的数据对象 0063 public Object put(Object key, Object value) { 0064 Object oldValue = A[h(key)].put(key, value); 0065 if (null == oldValue) { //若插入的条目未出现于原散列表中,则 0066 size++;//更新规模记录 0067 if (size > N * maxLemda) rehash();//若装填因子过大,则重散列 0068 } 0069 return oldValue; 0070 } 0071 0072 //若M中存在以key为关键码的条目,则删除之并返回其数据对象;否则,返回null 0073 public Object remove(Object key) { 0074 Object oldValue = A[h(key)].remove(key); 0075 if (null != oldValue) size--; 0076 return oldValue; 0077 } 0078 0079 //返回M中所有条目的一个迭代器 0080 //将各桶对应的映射结构的迭代器串接起来,构成整体的迭代器 0081 public Iterator entries() { 0082 List L = new List_DLNode(); 0083 for (int i = 0; i < N; i++) { 0084 Iterator it = A[i].entries(); 0085 while (it.hasNext()) L.insertLast(it.getNext()); 0086 } 0087 return new IteratorElement(L); 0088 } 0089 0090 //重散列 0091 private void rehash() { 0092 Iterator it = this.entries(); 0093 N = p(N << 1); 0094 A = new Map[N];//桶数组容量至少加倍 0095 for (int i = 0; i < N; i++) A[i] = new Map_DLNode(T); //为每个桶分配一个子映射 0096 while (it.hasNext()) {//将其对应的映射结构中的 0097 Entry e = (Entry)it.getNext();//各条目逐一取出,将其 0098 Object k = e.getKey();//关键码和 0099 Object v = e.getValue();//数据对象 0100 A[h(k)].put(k, v);//整合为新的条目,插入对应的子映射中 0101 } 0102 } 0103 }