首页 > 代码库 > 算法4-5:关联对数组的接口

算法4-5:关联对数组的接口

关联数组可以有两种操作:

  • 插入一个关键字和对应的值

  • 通过关键字查询与之对应的值


典型的应用有DNS查找。


接口


关联数组的接口如下:

public interface ST<Key,Value> {
    public Value get(Key key);
    public void remove(Key key);
    public boolean contains(Key key);
    public boolean isEmpty();
    public int size();
    public Iterable<Key> keys();
}


接口有以下规则:

  • 键值对中的数值不能为空

  • get()方法返回null表示key不存在

  • put()方法会覆盖现有的值


数据类型


Value的数据类型可以是任意的,但是Key的数据类型必须满足下列条件:

  • Key必须实现Comparable,也就是说可以比较

  • Key必须可以通过equals()函数进行比较

  • 最好使用不可变的数据类型作为关键字的数据类型。


等价测试


equals函数必须满足以下性质:

  • 反射性:x.equals(x)必须为true

  • 对称性:x.equals(y)和y.equals(x)是等价的

  • 传递性:x.equals(y) y.equals(z) 推出 x,equals(z)

  • 非空:x.equals(null)必须为false


等价必须满足以下条件:

  • 对象不是null

  • 对象的类型完全相同,继承的类型也不行

  • 关键的成员变量必须相同


代码模板

public final class Date implements Comparable<Data> {
    private final int month;
    private final int day;
    private final int year;
 
    public boolean equals(Object y) {
        if(y == this) return true;
 
        if(y == null) return false;
 
        if(y.getClass() != this.getClass()) return false;
 
        Date that = (Date) y;
        ...
    }
}


注意this的判断,null的判断,类型的判断。