大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > Java容器Set接口

Java容器Set接口

关键词:容器接口JavaSet  阅读(1157) 赞(18)

[摘要]本文是对Java容器Set接口的讲解,对学习Java编程技术有所帮助,与大家分享。

  Set接口的实现,可以方便地将指定的类型以集合类型保存在一个变量中。Set是一个不包含重复元素的Collection,更确切地讲,Set 不包含满足 e1.equals(e2) 的元素对,并且最多包含一个 null 元素。Set接口的底层存储实现都是依赖Map的实现,也可以说Set中元素的管理就是对Map中key的管理。下面简单描述一下各种Set接口的实现类,主要包括HashSet,LinkedHashSet,TreeSet

1、HashSet

  HashSet底层是有HashMap实现的,存储的是[key-Object常量]这样的键值对,同样包括initialCapacity和loadFactor两个参数,这两个参数的意义和HashMap一样,都是比较重要的。另外,HashSet集合里边的元素是无序的。

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
    map = new HashMap<E,Object>();
    }

    /**
     * Constructs a new set containing the elements in the specified
     * collection.  The <tt>HashMap</tt> is created with default load factor
     * (0.75) and an initial capacity sufficient to contain the elements in
     * the specified collection.
     *
     * @param c the collection whose elements are to be placed into this set
     * @throws NullPointerException if the specified collection is null
     */
    public HashSet(Collection<? extends E> c) {
    map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
    }

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * the specified initial capacity and the specified load factor.
     *
     * @param      initialCapacity   the initial capacity of the hash map
     * @param      loadFactor        the load factor of the hash map
     * @throws     IllegalArgumentException if the initial capacity is less
     *             than zero, or if the load factor is nonpositive
     */
    public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<E,Object>(initialCapacity, loadFactor);
    }

2、LinkedHashSet

  LinkedHashSet继承了HashSet,但它底层存储使用的是LinkedHashMap,所以其中的元素是按照插入有序的。看LinkedHashSet类只是定义了四个构造方法,也没看到和链表相关的内容,为什么说LinkedHashSet内部使用链表维护元素的插入顺序(插入的顺序)呢?点进去看下这个三个参数的构造方法HashSet(int initialCapacity, float loadFactor, boolean dummy),就会发现使用的实现类是LinkedHashMap了:

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private static final long serialVersionUID = -2851667679971038690L;

    /**
     * Constructs a new, empty linked hash set with the specified initial
     * capacity and load factor.
     *
     * @param      initialCapacity the initial capacity of the linked hash set
     * @param      loadFactor      the load factor of the linked hash set
     * @throws     IllegalArgumentException  if the initial capacity is less
     *               than zero, or if the load factor is nonpositive
     */
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }

    /**
     * Constructs a new, empty linked hash set with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param   initialCapacity   the initial capacity of the LinkedHashSet
     * @throws  IllegalArgumentException if the initial capacity is less
     *              than zero
     */
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    /**
     * Constructs a new, empty linked hash set with the default initial
     * capacity (16) and load factor (0.75).
     */
    public LinkedHashSet() {
        super(16, .75f, true);
    }
    /**
     * Constructs a new, empty linked hash set.  (This package private
     * constructor is only used by LinkedHashSet.) The backing
     * HashMap instance is a LinkedHashMap with the specified initial
     * capacity and the specified load factor.
     *
     * @param      initialCapacity   the initial capacity of the hash map
     * @param      loadFactor        the load factor of the hash map
     * @param      dummy             ignored (distinguishes this
     *             constructor from other int, float constructor.)
     * @throws     IllegalArgumentException if the initial capacity is less
     *             than zero, or if the load factor is nonpositive
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
    }

3、TreeSet

  TreeSet底层存储使用的是TreeMap,使用它可以从Set中提取有序的序列,元素必须实现Comparable接口否则按默认字典排序。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a set backed by the specified navigable map.
     */
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    /**
     * Constructs a new, empty tree set, sorted according to the
     * natural ordering of its elements.  All elements inserted into
     * the set must implement the {@link Comparable} interface.
     * Furthermore, all such elements must be <i>mutually
     * comparable</i>: {@code e1.compareTo(e2)} must not throw a
     * {@code ClassCastException} for any elements {@code e1} and
     * {@code e2} in the set.  If the user attempts to add an element
     * to the set that violates this constraint (for example, the user
     * attempts to add a string element to a set whose elements are
     * integers), the {@code add} call will throw a
     * {@code ClassCastException}.
     */
    public TreeSet() {
    this(new TreeMap<E,Object>());
    }

总结一下:

  HashSet是为快速查找而设计的Set,存入HashSet的元素必须定义hashCode();LinkedHashSet具有HashSet的查询速度,且内部使用链表维护元素的顺序(插入顺序),在使用迭代器遍历Set时,结果会按插入的次序显示,元素必须定义hashCode()方法;TreeSet保存次序的Set,底层为树结构,使用它可以从Set中提取有序的序列,元素必须实现Comparable接口。

  另外,这里提一下hashcode和equals在Set中的比较重要的意义。当对以哈希为底层的集合操作的时候,会先以hashcode去找对应的链表,然后再遍历对应的链表通过equals对比key,最后找到对应的value。还是和上次说的一样,当hashcode方法设计的不好的时候,会导致元素分布不均匀,然后调用大量的equals对比key,最后影响到程序的执行效率。

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

  最后提一下面试比较常问到的问题:当两个对象的hashcode相等的时候它们的equals不一定返回true;但当两个对象的equals返回true的时候它们的hashcode一定相同。



相关评论