参照数据结构--符号表API实现。
有序数组实现有序的符号表,使用一对平行的数组,一个保存键,一个保存值。键和值分别保存在两个数组的相同下标下,例如一个键值对,键保存在key3中,值就保存在val3中。这样,当我们查找时,找到键在key中的位置,就可以用下标去val[]数组中取到相应的值。而且,我们让Comparable类型的键有序,这样就可以用二分查找快速地在key数组中查找相应的键。
核心方法是rank()方法,它返回表中小于给定键的数量。只要给定的键在数组中,rank()方法就能精确的告诉我们去哪里找到它。因为把数组实现为有序的,所以可以通过二分查找来高效实现rank()方法。非递归方法和递归方法实现如下:
//非递归算法
public int rank(Key key) {
int lo = 0, hi = N-1;
while(lo<=hi) {
int mid = lo + (hi-lo)/2;
int cmp = key.compareTo(keys[mid]);
if(cmp<0) hi = mid-1;
if(cmp>0) lo = mid+1;
else return mid;
}
return lo;
}
//递归算法
public int rank(Key key, int lo, int hi) {
if(hi<lo) return lo;
int mid = lo + (hi-lo)/2;
int cmp = key.compareTo(keys[mid]);
if(cmp<0) return rank(key,lo,hi-1);
if(cmp>0) return rank(key,mid+1,hi);
else return mid;
}
在有了rank()方法后,get()方法很好实现。对于get()方法,只要给定的键存在,rank()方法能够精确给出目标下标;如果找不到,就是不存在。get()方法实现如下:
public Value get(Key key) {
if(isEmpty()) return null;
int i = rank(key);
if(i<N&&keys[i].compareTo(key)==0) return vals[i];
else return null;
}
对于put()方法,如果键存在,则要更新,rank()方法返回到哪里去更新;如果键不存在,则要插入,rank()方法给出在哪里插入;插入方法和数组排序算法相同,将所有更大的键先向后移动,然后把目标键值对插入相应位置。put()方法实现如下:
public void put(Key key,Value val) {
int i = rank(key);
if(i<N&&keys[i].compareTo(key)==0) {
vals[i] = val;return;
}
for(int j = N; j>i;j--) {
keys[j] = keys[j-1];vals[j] = vals[j-1];
}
keys[i] = key;vals[i] = val;
N++;
}
对于delete()方法,rank()返回要删除键值对的下标,然后将更大的键值对向前移一位即可:
public void delete(Key key) {//删除
if(isEmpty()) return;
int i = rank(key);
if(key.compareTo(keys[i])==0) {
for(int j = i;j<N;j++) {
keys[j] = keys[j+1];vals[j] = vals[j+1];
N--;
}
}
else return;
}
可以看出,基于有序数组实现符号表,查询操作效率提高了,但插入效率比较差。要高效支持插入操作,似乎需要一种链式结构,能够同时满足条件的就是二叉查找树。