2018-04-17

澳门新葡亰平台官网 6

总体介绍

如果你已看过前面关于HashSetHashMap,以及TreeSetTreeMap的讲解,一定能够想到本文将要讲解的LinkedHashSetLinkedHashMap其实也是一回事。LinkedHashSet澳门新葡亰平台官网,和LinkedHashMap在Java里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点分析LinkedHashMap

LinkedHashMap实现了Map接口,即允许放入keynull的元素,也允许插入valuenull的元素。从名字上可以看出该容器是linked
list
HashMap的混合体,也就是说它同时满足HashMaplinked
list
的某些特性。可将LinkedHashMap看作采用linked
list
增强的HashMap

澳门新葡亰平台官网 1

事实上LinkedHashMapHashMap的直接子类,二者唯一的区别是LinkedHashMapHashMap的基础上,采用双向链表(doubly-linked
list)的形式将所有entry连接起来,这样是为保证元素的迭代顺序跟插入顺序相同
。上图给出了LinkedHashMap的结构图,主体部分跟HashMap完全一样,多了header指向双向链表的头部(是一个哑元),该双向链表的迭代顺序就是entry的插入顺序

除了可以保迭代历顺序,这种结构还有一个好处:迭代LinkedHashMap时不需要像HashMap那样遍历整个table,而只需要直接遍历header指向的双向链表即可,也就是说LinkedHashMap的迭代时间就只跟entry的个数相关,而跟table的大小无关。

有两个参数可以影响LinkedHashMap的性能:初始容量(inital
capacity)和负载系数(load
factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时,容器将自动扩容并重新哈希。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。

将对象放入到LinkedHashMapLinkedHashSet中时,有两个方法需要特别关心:hashCode()equals()hashCode()方法决定了对象会被放到哪个bucket里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。所以,如果要将自定义的对象放入到LinkedHashMapLinkedHashSet中,需要*@Override*hashCode()equals()方法。

通过如下方式可以得到一个跟源Map**迭代顺序*一样的LinkedHashMap*:

void foo(Map m) {
    Map copy = new LinkedHashMap(m);

}

出于性能原因,LinkedHashMap是非同步的(not
synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过如下方式将LinkedHashMap包装成(wrapped)同步的:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

Java
LinkedHashMapHashMap有什么区别和联系?为什么LinkedHashMap会有着更快的迭代速度?LinkedHashSetLinkedHashMap有着怎样的内在联系?本文从数据结构和算法层面,结合生动图解为读者一一解答。

Java集合

★★★★★集合框架:用于存储数据的容器。

特点:

1:对象封装数据,对象多了也需要存储。集合用于存储对象。

2:对象的个数确定可以使用数组,但是不确定怎么办?可以用集合。因为集合是可变长度的。

集合和数组的区别:

1:数组是固定长度的;集合可变长度的。

2:数组可以存储基本数据类型,也可以存储引用数据类型;集合只能存储引用数据类型

3:数组存储的元素必须是同一个数据类型;集合存储的对象可以是不同数据类型。


数据结构:就是容器中存储数据的方式。

对于集合容器,有很多种。因为每一个容器的自身特点不同,其实原理在于每个容器的内部数据结构不同。

集合容器在不断向上抽取过程中。出现了集合体系。

在使用一个体系时,原则:参阅顶层内容。建立底层对象。



目录
1 Iterator接口
–1.1 Iterator
–1.2 ListIterator
2 Collection接口
–2.1 List接口
–2.2 Set接口
3 Map接口
4 综合总结
–4.1 集合工具Collections
–4.2 数组 Arrays
–4.3 LinkedHashSetLinkedHashMap比较



方法剖析

本文github地址

1 Iterator接口

get()

get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样,读者可自行参考前文,这里不再赘述。

总体介绍

如果你已看过前面关于HashSetHashMap,以及TreeSetTreeMap的讲解,一定能够想到本文将要讲解的LinkedHashSetLinkedHashMap其实也是一回事。LinkedHashSetLinkedHashMap在Java里也有着相同的实现,前者仅仅是对后者做了一层包装,也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。因此本文将重点分析LinkedHashMap

LinkedHashMap实现了Map接口,即允许放入keynull的元素,也允许插入valuenull的元素。从名字上可以看出该容器是linked
list
HashMap的混合体,也就是说它同时满足HashMaplinked
list
的某些特性。可将LinkedHashMap看作采用linked
list
增强的HashMap

澳门新葡亰平台官网 2

事实上LinkedHashMapHashMap的直接子类,二者唯一的区别是LinkedHashMapHashMap的基础上,采用双向链表(doubly-linked
list)的形式将所有entry连接起来,这样是为保证元素的迭代顺序跟插入顺序相同
。上图给出了LinkedHashMap的结构图,主体部分跟HashMap完全一样,多了header指向双向链表的头部(是一个哑元),该双向链表的迭代顺序就是entry的插入顺序

除了可以保迭代历顺序,这种结构还有一个好处:迭代LinkedHashMap时不需要像HashMap那样遍历整个table,而只需要直接遍历header指向的双向链表即可,也就是说LinkedHashMap的迭代时间就只跟entry的个数相关,而跟table的大小无关。

有两个参数可以影响LinkedHashMap的性能:初始容量(inital
capacity)和负载系数(load
factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当entry的数量超过capacity*load_factor时,容器将自动扩容并重新哈希。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。

将对象放入到LinkedHashMapLinkedHashSet中时,有两个方法需要特别关心:hashCode()equals()hashCode()方法决定了对象会被放到哪个bucket里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。所以,如果要将自定义的对象放入到LinkedHashMapLinkedHashSet中,需要*@Override*hashCode()equals()方法。

通过如下方式可以得到一个跟源Map 迭代顺序一样的LinkedHashMap

void foo(Map m) {
    Map copy = new LinkedHashMap(m);
    ...
}

出于性能原因,LinkedHashMap是非同步的(not
synchronized),如果需要在多线程环境使用,需要程序员手动同步;或者通过如下方式将LinkedHashMap包装成(wrapped)同步的:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

1.1 Iterator

< java.util >–
迭代器:是一个接口—Iterator接口,其作用:用于取集合中的元素。

在Iterator接口中定义了三个方法:

boolean hasNext() 如果仍有元素可以迭代,则返回true
E next() 返回迭代的下一个元素。
void remove() 从迭代器指向的 collection 中移除迭代器返回的最后一个元素(可选操作)。

每一个集合都有自己的数据结构(就是容器中存储数据的方式),都有特定的取出自己内部元素的方式。为了便于操作所有的容器,取出元素。将容器内部的取出方式按照一个统一的规则向外提供,这个规则就是Iterator接口,使得对容器的遍历操作与其具体的底层实现相隔离,达到解耦的效果。

也就说,只要通过该接口就可以取出Collection集合中的元素,至于每一个具体的容器依据自己的数据结构,如何实现的具体取出细节,这个不用关心,这样就降低了取出元素和具体集合的耦合性。

Iterator it =
coll.iterator();
//获取容器中的迭代器对象,至于这个对象是是什么不重要。这对象肯定符合一个规则Iterator接口。

public static void main(String[] args) {
       Collection coll = new ArrayList();
       coll.add("abc0");
       coll.add("abc1");
       coll.add("abc2");
       //--------------方式1----------------------
       Iterator it = coll.iterator();
       while(it.hasNext()){
           System.out.println(it.next());
       }
       //---------------方式2用此种----------------------
       for(Iterator it =coll.iterator();it.hasNext(); ){
           System.out.println(it.next());
       }
 }

使用Iterator迭代器来进行删除,则不会出现并发修改异常。

因为:在执行remove操作时,同样先执行checkForComodification(),然后会执行ArrayList的remove()方法,该方法会将modCount值加1,这里我们将expectedModCount=modCount,使之保持统一。

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于get()方法;如果没有找到,则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry

注意,这里的插入有两重含义

  1. table的角度看,新的entry需要插入到对应的bucket里,当有哈希冲突时,采用头插法将新的entry插入到冲突链表的头部。
  2. header的角度看,新的entry需要插入到双向链表的尾部。

澳门新葡亰平台官网 3

addEntry()代码如下:

// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容,并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面,这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:

// LinkedHashMap.Entry.addBefor(),将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

上述代码只是简单修改相关entry的引用而已。

方法剖析

1.2 ListIterator

上面可以看到,Iterator只提供了删除元素的方法remove,如果我们想要在遍历的时候添加元素怎么办?

ListIterator接口继承了Iterator接口,它允许程序员按照任一方向遍历列表,迭代期间修改列表,并获得迭代器在列表中的当前位置。

使用ListIterator来对list进行边遍历边添加元素操作:

public static void main(String[] args)
    {
       ArrayList<String> aList = new ArrayList<String>();
       aList.add("bbc");
       aList.add("abc");
       aList.add("ysc");
       aList.add("saa");
       System.out.println("移除前:" + aList);
       ListIterator<String> listIt = aList.listIterator();
        while(listIt.hasNext())
        {
            if("abc".equals(listIt.next()))
            {
               listIt.add("haha");
            }
        }
       System.out.println("移除后:" + aList);
    }

remove()

remove(Object key)的作用是删除key值对应的entry,该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry,然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。

注意,这里的删除也有两重含义

  1. table的角度看,需要将该entry从对应的bucket里删除,如果对应的冲突链表不空,需要修改冲突链表的相应引用。
  2. header的角度来看,需要将该entry从双向链表中删除,同时修改链表中前面以及后面元素的相应引用。

澳门新葡亰平台官网 4

removeEntryForKey()对应的代码如下:

// LinkedHashMap.removeEntryForKey(),删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {

    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry<K,V> prev = table[i];// 得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {// 遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

get()

get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样,读者可自行参考前文,这里不再赘述。

2 Collection接口

–< java.util >–Collection接口:

Collection:

|–List:有序(元素存入集合的顺序和取出的顺序一致),元素都有索引。元素可以重复。

|–Set:无序(存入和取出顺序有可能不一致),不可以存储重复元素。必须保证元素唯一性。

1.添加:

​ add(object):添加一个元素

​ addAll(Collection) :添加一个集合中的所有元素。

2.删除:

​ clear():将集合中的元素全删除,清空集合

​ remove(obj)
:删除集合中指定的对象。注意:删除成功,集合的长度会改变。

​ removeAll(collection) :删除部分元素。部分元素和传入Collection一致。

3.判断:

​ boolean contains(obj) :集合中是否包含指定元素 。

​ boolean containsAll(Collection) :集合中是否包含指定的多个元素。

​ boolean isEmpty():集合中是否有元素。

4.获取:

​ int size():集合中有几个元素。

5.取交集:

​ boolean retainAll(Collection)
:对当前集合中保留和指定集合中的相同的元素。如果两个集合元素相同,返回flase;如果retainAll修改了当前集合,返回true。

6.获取集合中所有元素:

Iterator iterator()迭代器

7.将集合变成数组:

​ toArray();


LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装,对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法,因此LinkedHashSet的实现非常简单,这里不再赘述。

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

    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }

}

put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法首先会对map做一次查找,看是否包含该元组,如果已经包含则直接返回,查找过程类似于get()方法;如果没有找到,则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry

注意,这里的插入有两重含义

  1. table的角度看,新的entry需要插入到对应的bucket里,当有哈希冲突时,采用头插法将新的entry插入到冲突链表的头部。
  2. header的角度看,新的entry需要插入到双向链表的尾部。

澳门新葡亰平台官网 5

addEntry()代码如下:

// LinkedHashMap.addEntry()
void addEntry(int hash, K key, V value, int bucketIndex) {
    if ((size >= threshold) && (null != table[bucketIndex])) {
        resize(2 * table.length);// 自动扩容,并重新哈希
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = hash & (table.length-1);// hash%table.length
    }
    // 1.在冲突链表头部插入新的entry
    HashMap.Entry<K,V> old = table[bucketIndex];
    Entry<K,V> e = new Entry<>(hash, key, value, old);
    table[bucketIndex] = e;
    // 2.在双向链表的尾部插入新的entry
    e.addBefore(header);
    size++;
}

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面,这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:

// LinkedHashMap.Entry.addBefor(),将this插入到existingEntry的前面
private void addBefore(Entry<K,V> existingEntry) {
    after  = existingEntry;
    before = existingEntry.before;
    before.after = this;
    after.before = this;
}

上述代码只是简单修改相关entry的引用而已。

2.1 List接口

–< java.util >– List接口:

List本身是Collection接口的子接口,具备了Collection的所有方法。现在学习List体系特有的共性方法,查阅方法发现List的特有方法都有索引,这是该集合最大的特点。

List有序(元素存入集合的顺序和取出的顺序一致)元素都有索引。元素可以重复。(有序可重复)

|–ArrayList:底层的数据结构是数组,线程不同步,ArrayList替代了Vector,查询元素的速度非常快。默认大小10,1.5倍长度扩容。

|–LinkedList:底层的数据结构是链表,线程不同步,增删元素的速度非常快。

|–Vector:底层的数据结构就是数组,线程同步,Vector无论查询和增删都巨慢。默认大小10,2倍长度扩容。

1.添加:

​ add(index,element) :在指定的索引位插入元素。

​ addAll(index,collection) :在指定的索引位插入一堆元素。

2.删除:

​ remove(index) :删除指定索引位的元素。 返回被删的元素。

3.获取:

​ Object get(index) :通过索引获取指定元素。

​ int
indexOf(obj):获取指定元素第一次出现的索引位,如果该元素不存在返回-1;

​ 所以,通过-1,可以判断一个元素是否存在。

​ int lastIndexOf(Object o) :反向索引指定元素的位置。

​ List subList(start,end):获取子列表。

4.修改:

​ Object set(index,element) :对指定索引位进行元素的修改。

5.获取所有元素:

​ ListIterator listIterator():list集合特有的迭代器。

List集合支持对元素的增、删、改、查。

List集合因为角标有了自己的获取元素的方式: 遍历。

for(int x=0;x<list.size(); x++){

sop(“get:”+list.get(x));

}

在进行list列表元素迭代的时候,如果想要在迭代过程中,想要对元素进行操作的时候,比如满足条件添加新元素。会发生.ConcurrentModificationException并发修改异常。

导致的原因是:

集合引用和迭代器引用在同时操作元素,通过集合获取到对应的迭代器后,在迭代中,进行集合引用的元素添加,迭代器并不知道,所以会出现异常情况。

如何解决呢?

既然是在迭代中对元素进行操作,找迭代器的方法最为合适.可是Iterator中只有hasNext,next,remove方法.通过查阅的它的子接口,ListIterator,发现该列表迭代器接口具备了对元素的增、删、改、查的动作。

ListIterator是List集合特有的迭代器

ListIterator it =list.listIterator;//取代Iterator it = list.iterator;

方法摘要
void add(Ee)将指定的元素插入列表(可选操作)。
boolean hasNext()以正向遍历列表时,如果列表迭代器有多个元素,则返回true(换句话说,如果 next 返回一个元素而不是抛出异常,则返回 true)。
boolean hasPrevious()如果以逆向遍历列表,列表迭代器有多个元素,则返回true
E next()返回列表中的下一个元素。
int nextIndex()返回对 next 的后续调用所返回元素的索引。
E previous()返回列表中的前一个元素。
int previousIndex()返回对previous 的后续调用所返回元素的索引。
void remove()从列表中移除由 nextprevious 返回的最后一个元素(可选操作)。
void set(Ee)用指定元素替换 nextprevious 返回的最后一个元素(可选操作)。

可变长度数组的原理:

当元素超出数组长度,会产生一个新数组,将原数组的数据复制到新数组中,再将新的元素添加到新数组中。

ArrayList:是按照原数组的50%延长。构造一个初始容量为 10 的空列表。

Vector:是按照原数组的100%延长。

注意:对于list集合,底层判断元素是否相同,其实用的是元素自身的equals方法完成的。所以建议元素都要复写equals方法,建立元素对象自己的比较相同的条件依据。

LinkedList:的特有方法。

addFirst();

addLast();

在jdk1.6以后。

offerFirst();

offerLast();

getFirst():获取链表中的第一个元素。如果链表为空,抛出NoSuchElementException;

getLast();获取链表中的最后一个元素。如果链表为空,抛出NoSuchElementException;

在jdk1.6以后。

peekFirst();获取链表中的第一个元素。如果链表为空,返回null。

peekLast();

removeFirst():获取链表中的第一个元素,但是会删除链表中的第一个元素。如果链表为空,抛出NoSuchElementException

removeLast();

在jdk1.6以后。

pollFirst();获取链表中的第一个元素,但是会删除链表中的第一个元素。如果链表为空,返回null。

pollLast();

remove()

remove(Object key)的作用是删除key值对应的entry,该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会首先找到key值对应的entry,然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。

注意,这里的删除也有两重含义

  1. table的角度看,需要将该entry从对应的bucket里删除,如果对应的冲突链表不空,需要修改冲突链表的相应引用。
  2. header的角度来看,需要将该entry从双向链表中删除,同时修改链表中前面以及后面元素的相应引用。

澳门新葡亰平台官网 6

removeEntryForKey()对应的代码如下:

// LinkedHashMap.removeEntryForKey(),删除key值对应的entry
final Entry<K,V> removeEntryForKey(Object key) {
    ......
    int hash = (key == null) ? 0 : hash(key);
    int i = indexFor(hash, table.length);// hash&(table.length-1)
    Entry<K,V> prev = table[i];// 得到冲突链表
    Entry<K,V> e = prev;
    while (e != null) {// 遍历冲突链表
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
            modCount++; size--;
            // 1. 将e从对应bucket的冲突链表中删除
            if (prev == e) table[i] = next;
            else prev.next = next;
            // 2. 将e从双向链表中删除
            e.before.after = e.after;
            e.after.before = e.before;
            return e;
        }
        prev = e; e = next;
    }
    return e;
}

2.2 Set接口

< java.util >–
Set集合无序,add()相同元素则添加失败,返回flase。:

数据结构:数据的存储方式;

Set接口中的方法和Collection中方法一致的。Set接口取出方式只有一种,迭代器

|–HashSet:底层数据结构是哈希表,HashSet是集合,无序,高效线程不同步。


|–LinkedHashSet:存取顺序一致(用链表维护),线程不同步,是hashset的子类。

|–TreeSet:元素唯一,有序(按照元素自身执行顺序),线程不同步(不按原有数组的顺序)。TreeSet底层的数据结构就是二叉树(平衡二叉排序树)。

|–EnumSet 只能保存同一类型元素。

HashSet、TreeSet、LinkedHashSet的区别:HashSet只去重,TreeSet去重并排序,LinkedHashSet去重并保留插入顺序

===HashSet 哈希表原理===

采用哈希表存储结构。

1:对对象元素中的关键字进行哈希算法运算,得结果为哈希值(也是这个元素的位置

2:存储哈希值的结构,我们称为哈希表,在哈希表中查找对应的哈希值对应位置,

3:如果哈希值出现冲突,再次判断这个关键字对应的对象是否相同:

如果对象相同,就不存储,因为元素重复;

如果对象不同,就存储,在原来对象的哈希值基础** +1顺延**。

4:既然哈希表根据哈希值存储,为提高效率,最好保证对象关键字的唯一性。
可尽量少的判断关键字对应的对象是否相同,提高了哈希表的操作效率。

高效:保证关键字唯一性,即为上述第三步所述,也可以用以下叙述:

HashSet集合保证元素唯一性:通过元素的hashCode()equals()完成的。

​ 当元素的hashCode值相同时,才继续判断元素的equals是否为true。

​ 如果为true,那么视为相同元素,不存。如果为false,那么存储。

​ 如果hashCode值不同,那么不判断equals,从而提高对象比较的速度。

对于ArrayList集合,判断元素是否存在,或者删元素底层依据都是equals方法。

对于HashSet集合,判断元素是否存在,或者删除元素,底层依据的是hashCode方法和equals方法。

===TreeSet原理===

采用二叉树(二叉平衡排序树)存储结构 (或红黑树)

TreeSet用于对Set集合进行元素的指定顺序排序,要依据元素自身的比较性(
如果元素不具备比较性,在运行时会发生ClassCastException异常)所以需要元素实现Comparable接口复写compareTo方法(根据指定需求),强制让对象元素具备比较性,否则比较时引发ClassCastException异常。

TreeSet支持两种排序方法:自然排序和定制排序;默认采用自然排序。

原理:当把一个对象添(必须实现Comparable接口)加进TreeSet时,TreeSet调用该对象的compareTo(Objectobj)方法与容器中的其他对象比较大小,然后根据红黑树算法决定它的存储位置
如果两个对象通过compareTo(Object obj)比较相等,return
0,视为两对象重复,不存储。(通过此方法保证了对象的唯一性

注意:在进行比较时,如果判断元素不唯一,比如,同姓名,同年龄,才视为同一个人。

在判断时,需要分主要、次要条件,当主要条件相同时,再判断次要条件,按照次要条件排序。

TreeSet集合排序有两种方式,Comparable和Comparator区别:

1:让元素自身具备比较性,需要元素对象实现Comparable接口,覆盖compareTo方法。

2:让集合自身具备比较性,需要定义一个实现了Comparator接口的比较器,并覆盖compare方法,并将该类对象作为实际参数传递给TreeSet集合的构造函数。第二种方式较为灵活。

LinkedHashSet

前面已经说过LinkedHashSet是对LinkedHashMap的简单包装,对LinkedHashSet的函数调用都会转换成合适的LinkedHashMap方法,因此LinkedHashSet的实现非常简单,这里不再赘述。

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
    ......
    // LinkedHashSet里面有一个LinkedHashMap
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    ......
    public boolean add(E e) {//简单的方法转换
        return map.put(e, PRESENT)==null;
    }
    ......
}

3 Map接口

Map

|–Hashtable:底层是哈希散列表数据结构,线程同步。不可以存储null键,null值。不可序列化,使用bucket结构体表示单个元素,使用双重散列法(闭散列法)解决冲突(二度哈希,size>length时要进行模运算)。

|–HashMap:底层是哈希表数据结构(链地址法解决冲突),线程不同步。可存一个null键和多个null值。替代了Hashtable.
但可通过Map m = Collections.synchronizeMap(hashMap)实现同步;


|–LinkedHashMap,采用双向链表数据结构连接起来所有的entry,保证了存入和取出顺序一致,即链表有序;线程不同步。

|–TreeMap:底层是二叉树结构(平衡二叉排序树),可以对map集合中的键进行指定顺序的排序。


Map集合存储和Collection有着很大不同:

Collection一次存一个元素,是单列集合;

Map一次存一对元素,是双列集合。Map存储的一对元素:键–值,键(key)与值(value)间有对应(映射)关系。

特点:要保证Map中键的唯一性。

1:添加。

put(key,value):当存储的键相同时,新的值会替换老的值,并将老值返回。如果键没有重复,返回null。

void putAll(Map);

2:删除。

void clear():清空

value remove(key) :删除指定键。

3:判断。

boolean isEmpty():

boolean containsKey(key):是否包含key

boolean containsValue(value):是否包含value

4:取出。

int size():返回长度

value get(key)
:通过指定键获取对应的值。如果返回null,可以判断该键不存在。当然有特殊情况,就是在hashmap集合中,是可以存储null键null值的。

Collection values():获取map集合中的所有的值。

5:想要获取map中的所有元素

原理:map没有迭代器,collection具备迭代器,只要将map转成Set集合,就可使用迭代器。之所以转成set,是因为map集合具备键的唯一性,其实set集合就来自于map,set集合底层其实用的就是map的方法。

把map集合转成set的方法:(决定了两种遍历方式)

Set keySet();

Set entrySet();//取的是键和值的映射关系。

Entry就是Map接口中的内部接口;

为什么要定义在map内部呢?entry是访问键值关系的入口,是map的入口,访问的是map中的键值对。


取出map集合中所有元素的方式一:keySet()方法。

可以将map集合中的键都取出存放到set集合中。对set集合进行迭代。迭代完成,再通过get方法对获取到的键进行值的获取。

  Set keySet = map.keySet();
      Iterator it = keySet.iterator();
      while(it.hasNext()) {
          Object key = it.next();
          Objectvalue = map.get(key);
          System.out.println(key+":"+value);  
      }

取出map集合中所有元素的方式二:entrySet()方法。

Set entrySet = map.entrySet();
       Iterator it =entrySet.iterator();
       while(it.hasNext()) {
           Map.Entry  me =(Map.Entry)it.next();
           System.out.println(me.getKey()+"::::"+me.getValue());
       }

使用集合的技巧:

看到Array就是数组结构,有角标,查询速度很快。

看到link就是链表结构:增删速度快,而且有特有方法。addFirst;
addLast;removeFirst(); removeLast();getFirst();getLast();

看到hash就是哈希表,就要想要哈希值,就要想到唯一性,就要想到存入到该结构中的元素必须覆盖hashCode和equals方法。

看到tree就是二叉树,就要想到排序,就想要用到比较。


比较的两种方式:

一个是Comparable:覆盖compareTo方法;

一个是Comparator:覆盖compare方法。

LinkedHashSet,LinkedHashMap:这两个集合可以保证哈希表有存入顺序和取出顺序一致,保证哈希表有序。


集合使用场景?

当存储一个元素时,用Collection。当存储对象之间存在着映射关系时,用Map集合。

保证唯一,就用Set。不保证唯一,就用List。


4 综合总结

4.1 集合工具Collections

Collections:集合工具类,它的出现给集合操作提供了更多的功能。这个类不需要创建对象,内部提供的都是静态方法。

静态方法:

Collections.sort(list);//list集合进行元素的自然顺序排序。

Collections.sort(list,new
ComparatorByLen()
);//按指定的比较器方法排序。

class ComparatorByLen implements Comparator<String>{

public int compare(String s1,String s2){

​ int temp = s1.length()-s2.length();

​ return temp==0?s1.compareTo(s2):temp;

}

}

Collections.max(list);//返回list中字典顺序最大的元素。

int index =
Collections.binarySearch(list,”zz”);//二分查找,返回角标。

Collections.reverseOrder();//逆向反转排序。

Collections.shuffle(list);//随机对list中的元素进行位置的置换。

将非同步集合转成同步集合的方法:Collections中的 XXX
synchronizedXXX(XXX);

List synchronizedList(list);

Map synchronizedMap(map);

原理:定义一个类,将集合所有的方法加同一把锁后返回。

Collection 和 Collections的区别:

Collections是个java.util下的类,是针对集合类的一个工具类,提供一系列静态方法,实现对集合的查找、排序、替换、线程安全化(将非同步的集合转换成同步的)等操作。

Collection是个java.util下的接口,它是各种集合结构的父接口,继承于它的接口主要有Set和List,提供了关于集合的一些操作,如插入、删除、判断一个元素是否其成员、遍历等。

4.2 数组 Arrays

用于操作数组对象的工具类,里面都是静态方法。

数组=》集合asList方法将数组转换成list集合。

String[] arr ={“abc”,”kk”,”qq”};

List<String> list =Arrays.asList(arr);//将arr数组转成list集合。

将数组转换成集合,有什么好处呢?用aslist方法,将数组变成集合;

可以通过list集合中的方法来操作数组中的元素:isEmpty()、contains、indexOf、set;

注意(局限性):数组是固定长度,不可以使用集合对象增加或者删除等,会改变数组长度的功能方法。比如add、remove、clear。(会报不支持操作异常UnsupportedOperationException);

如果数组中存储的引用数据类型,直接作为集合的元素可以直接用集合方法操作。

如果数组中存储的是基本数据类型,asList会将数组实体作为集合元素存在。

集合=》数组:用的是Collection接口中的toArray()方法;

如果给toArray传递的指定类型的数据长度小于了集合的size,那么toArray方法,会自定再创建一个该类型的数据,长度为集合的size。


如果传递的指定的类型的数组的长度大于了集合的size,那么toArray方法,就不会创建新数组,直接使用该数组即可,并将集合中的元素存储到数组中,其他为存储元素的位置默认值null。

​ 所以,在传递指定类型数组时,最好的方式就是指定的长度和size相等的数组。

将集合变成数组后有什么好处?限定了对集合中的元素进行增删操作,只要获取这些元素即可。

4.3 LinkedHashSetLinkedHashMap比较

两者实现相同,只是前者对后者做了一层包装,即LinkedHashSet里面有一个LinkedHashMap(适配器模式)。下面说其实现。

LinkedHashMap,可存null键null值,从名字上可以看出是linkedlistHashMap的混合体,同时满足HashMaplinked
list
的某些特性。可将LinkedHashMap看作采用linked
list
增强的HashMap

事实上LinkedHashMapHashMap的直接子类,LinkedHashMapHashMap的基础上采用双向链表(doubly-linked
list)的形式将所有entry连接起来,保证元素的迭代顺序跟插入顺序相同。

除了迭代顺序不变,还有一个好处:迭代时不需要遍历整个table,只需要直接遍历header指针指向的双向链表即可,(LinkedHashMap的迭代时间就只跟entry的个数相关,而跟table的大小无关。)

有两个参数可以影响LinkedHashMap的性能:初始容量(initalcapacity)和负载系数(load
factor)。初始容量指定了初始table的大小,负载系数用来指定自动扩容的临界值。当entry的数量超过capacityload_factor时,容器将自动扩容并重新哈希*。对于插入元素较多的场景,将初始容量设大可以减少重新哈希的次数。

向LinkedHashMapLinkedHashSet添加对象时,需要关心两个方法:hashCode()方法决定了对象会被放到哪个bucket里,当多个对象的哈希值冲突时,equals()方法决定了这些对象是否是“同一个对象”。此时需要将自定义的对象
@OverridehashCode()和equals()方法。

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图