찾다

집  >  기사  >  Java  >  Java 컬렉션(1) - 데이터 구조에 대한 자세한 설명

Java 컬렉션(1) - 데이터 구조에 대한 자세한 설명

黄舟
黄舟원래의
2017-03-01 11:53:131876검색


C++ 및 C의 배열 및 포인터와 비교하여 데이터 문자열을 처리하려는 경우 Java에서는 ArrayList 및 HashMap과 같은 컬렉션 데이터 구조를 더 일반적으로 사용합니다. 포인터에 대한 C 언어의 지원은 그 깊이에 기여하는 반면, Java의 다양한 래퍼 클래스는 그 폭을 넓히는 데 기여합니다. Java에서는 일반적으로 List, Map, Set 등의 데이터 구조를 컬렉션 데이터 구조로 분류합니다. 이러한 클래스는 컬렉션 클래스 라이브러리에 존재합니다.

(1) 컬렉션 인터페이스

1. 컬렉션의 인터페이스와 구현은

다른 데이터 구조 라이브러리와 분리됩니다. 마찬가지로 Java의 컬렉션 클래스 라이브러리도 이러한 인터페이스와 구현 분리 방법을 채택합니다.

이 방법의 이점은 자명합니다. 큐를 인스턴스화하려는 경우, 체인 구조나 루프 배열 또는 기타 다른 구현 방법을 선택하려면 컬렉션 인터페이스에 대해 다른 구현 클래스를 참조하면 됩니다. 

Queue<String> qe1 = new LinkedList<>();
//LinkedList是链表实现队列Queue<String> qe2 = new ArrayDeque<>();
//ArrayDeque是循环数组实现队列

도 Queue의 구현 클래스이지만 방식이 다릅니다.

2. 컬렉션 인터페이스

컬렉션 클래스 라이브러리에서 가장 기본적인 인터페이스는 컬렉션 인터페이스입니다.

컬렉션 인터페이스는 다른 모든 클래스가 진화하는 컬렉션 클래스 라이브러리 트리의 루트로 이해될 수 있습니다. Colleaction은 일반 인터페이스이기 때문에 Java 클래스 라이브러리의 디자이너는 이 일반 인터페이스에 많은 메서드를 추가했으며 모든 구현 클래스는 이러한 메서드를 구현해야 합니다. 

int size()
//返回此 collection 中的元素数。
//如果此 collection 包含的元素大于 Integer.MAX_VALUE，则返回 Integer.MAX_VALUE。boolean isEmpty()
//如果此 collection 不包含元素，则返回 true。 boolean contains(Object o)
//当且仅当此 collection 至少包含一个满足 (o==null ? e==null : o.equals(e)) 的元素 e 时，返回 true。 Iterator<E> iterator()
//返回在此 collection 的元素上进行迭代的迭代器。//关于元素返回的顺序没有任何保证,除非此 collection 是某个能提供保证顺序的类实例。 Object[] toArray()
//返回包含此 collection 中所有元素的数组。//如果 collection 对其迭代器返回的元素顺序做出了某些保证，那么此方法必须以相同的顺序返回这些元素。 
//返回的数组将是“安全的”，因为此 collection 并不维护对返回数组的任何引用。//调用者可以随意修改返回的数组。 
//此方法充当了基于数组的 API 与基于 collection 的 API 之间的桥梁。 boolean add(E e)
//确保此 collection 包含指定的元素。如果此 collection 由于调用而发生更改，则返回 true。
//如果此 collection 不允许有重复元素，并且已经包含了指定的元素，则返回 false。boolean remove(Object o)
//如果此 collection 包含一个或多个满足 (o==null ? e==null : o.equals(e)) 的元素 e，则移除这样的元素。
//如果此 collection 包含指定的元素（或者此 collection 由于调用而发生更改），则返回 true 。 boolean containsAll(Collection<?> c)
//如果此 collection 包含指定 collection 中的所有元素，则返回 true。 boolean addAll(Collection<? extends E> c)
//将指定 collection 中的所有元素都添加到此 collection 中。
//如果在进行此操作的同时修改指定的 collection，那么此操作行为是不确定的。boolean removeAll(Collection<?> c)
//移除此 collection 中那些也包含在指定 collection 中的所有元素。
//此调用返回后，collection 中将不包含任何与指定 collection 相同的元素。 void clear()
//移除此 collection 中的所有元素。boolean retainAll(Collection<?> c)
//仅保留此 collection 中那些也包含在指定 collection 的元素。
//移除此 collection 中未包含在指定 collection 中的所有元素。

위 메소드는 모든 컬렉션 데이터 구조에 나타납니다. 어떤 데이터 구조이든 호출하기만 하면 아무런 문제가 없습니다. 게다가, Java API 작성자의 수준은 정말 감탄할 수밖에 없습니다. 메소드 함수의 도입은 최소한의 언어에서도 완벽합니다. 특히 제거에서의 판단 방법은 null의 존재를 포함하여 서면으로 간단하고 아름답습니다. (특히 테이블은 Collection 인터페이스가 아닌 Map 인터페이스에서 구현됩니다)

(2) Iterator

Collection 인터페이스를 생성하면서 collection 클래스 라이브러리 또한 Iterator 인터페이스가 생성됩니다. 이 인터페이스의 객체는 컬렉션의 모든 요소를 ​​순서대로 탐색하는 반복자입니다. 처음에 컬렉션이 정렬되면 Collection 인터페이스의 iterator 메서드를 통해 반환된 반복자 객체는 컬렉션 의 시작 위치에 있게 됩니다. 

Iterator<Integer> it = new Iterator<>();
Iterator<Integer> it = queue.iterator();
//通过队列中实现的iterator方法返回迭代器

Iterator 객체는 컬렉션의 각 객체를 블록으로 처리하여 작동하며 이러한 블록 사이를 점프합니다. 처음에는 첫 번째 블록 앞에 있습니다(순서가 지정된 집합인 경우). next() 메서드를 한 번 호출하면 다음 블록으로 점프하고 점프 후에는 해당 블록으로 돌아갑니다. 그 앞에. 처음에 it.remove()를 직접 실행하면 오류가 발생합니다. 제거의 원칙은 앞에 있는 블록을 삭제하는 것이므로 next() 작업을 먼저 수행해야 합니다. 같은 방식으로 두 번 연속으로 제거하면 오류가 보고됩니다. 

Queue<Integer> qe1 = new LinkedList<>();

qe1.add(null);  
qe1.add(1);
qe1.add(20);
System.out.println(qe1);Iterator<Integer> it = qe1.iterator();
//-------------error-------------it.reomve();  
//不能直接调用remove()，这时it没有跳过块，it之前没有内容
//-------------------------------
//-------------error-------------it.next();
it.remove();
it.reomve();  
//不能连续调用remove()，it之前的块已被删除，再调用报错
//-------------------------------
//--------------ok---------------it.next();
it.remove();
it.next();
it.remove();
//-------------------------------System.out.println(qe1);
//输出：//[20]

위의 예에서 주목할 만한 한 가지는

이 완전히 사실이라는 것입니다. 기본적으로 모든 컬렉션은 null을 객체로 명시적으로 전달할 수 있습니다(PriorityQueue...등과 같은 특수 컬렉션은 제외). 이런 식으로 API도 이해할 수 있습니다: qe1.add(null);

if(o==null ? e==null : o.equals(e)) //如果集合中有和o相同的e

(3) LinkedList

배열 및 동적 ArrayList 배열은 노드 삭제 비용이 높다는 문제를 안고 있으며, 연결리스트(Linked List)의 출현으로 이 문제가 해결되었습니다. Java의 모든 연결 목록은 실제로 양방향이며, 이전 노드에 대한 참조, 저장된 개체 및 후속 노드에 대한 참조를 포함합니다. 

List<String> letter = new LinkedList<>(); //链表

1. ListIterator

연결된 목록을 사용할 때는 추가 및 삭제 기능을 많이 수행해야 한다는 의미였습니다. 연결된 목록과 같은 정렬된 컬렉션의 경우 Iterator는 의심할 여지 없이 위치를 설명하는 가장 좋은 클래스이지만 Iterator에는 add 메서드가 없습니다(특정 위치에 요소를 추가할 필요가 없는 정렬되지 않은 집합이 많기 때문에). 그래서 구현합니다. Iterator에서 추가 및 삭제 작업을 수행하기 위해 하위 클래스인 ListIterator가 생성됩니다. 

package Collection;import java.util.LinkedList;import java.util.List;import java.util.ListIterator;/**
 * 
 * @author QuinnNorris
 * 链表LinkedList的操作，以及ListIterator
 */public class LinkedListE {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        List<String> letter = new LinkedList<>();

        letter.add(0, "a"); //在索引为0的位置添加元素
        letter.add("b");
        letter.add("c");
        letter.add("d");

        ListIterator li = letter.listIterator(2);//在第3个元素“c”（索引为2）之前放置迭代器
        li.previous();//迭代器向前遍历
        li.remove();//删除刚刚跳过的元素“b”

        li.next();//迭代器向后遍历
        li.remove();//删除刚刚跳过的元素“c”

        li.next();//迭代器向后遍历
        li.set("e");//将刚刚跳过的元素“d”重新设置为“e”

        System.out.println(li.nextIndex());//输出： 2
        System.out.println(li.previousIndex());//输出：1

        System.out.println(letter);//输出：[a,e]

        letter.get(0);//可以使用，但是不要这样做
    }

}

ListIterator는 요소를 앞으로 순회하는 이전() 메서드를 제공하고 새로 고침 메서드인 set()을 제공합니다. set 메소드는 방금 건너뛴 노드의 내용을 재설정할 수 있으며, 이 메소드에는 특별한 점이 있으며 앞으로 여러 번 사용할 것입니다.

2. 연결 목록의 Get 및 set 메서드

연결 목록에서 get() 메서드를 자주 호출하면 이미 잘못된 길. get 메소드의 구현 효율성은 쿼리 요구 사항보다 추가 및 삭제 요구 사항이 더 많은 테이블이 아닌 경우 다른 테이블 사용을 고려해야 할 때입니다.

(4) 동적 배열 목록 ArrayList

위의 연결 목록에서 해당되지 않는 set 및 get 메소드는 ArrayList에서 매우 유용합니다. 이 클래스는 List 인터페이스도 구현합니다. 이 목록은 우리가 꽤 많이 사용하는 목록일 수 있습니다. 동기화가 필요하지 않은 경우 ArrayList는 가장 신뢰할 수 있는 작은 도우미입니다.

(5) HashSet

순서를 고려하지 않고 일부 요소만 세트에 저장하려면 해시를 사용할 수 있습니다. 열 세트를 사용하여 저장합니다. 이러한 요소는 빠르게 찾을 수 있습니다. 단점은 순서를 제어할 수 없다는 것입니다.

1.散列表原理

HashTable是非常出名的数据结构，它的存放对象的原理大概是这样的：

  1. 将每个对象设置一个散列码（有的通过HashCode()方法）。

  2. 实现许多条链表数组，将每条这样的数组称为一个桶（bucket）。

  3. 将对象的散列码与桶的总数取余，得到的余数就是保存这个对象的桶的索引。

  4. 将这个对象放入这个桶中，如果这个桶此时无对象，则他作为第一个节点，否则跟在最后一个节点后面

  5. 如果这个桶被占满，发生散列冲突。java会先尝试扩充链表，如果不行，一般采用链表法，继续向后延展。

2.散列表中一些预防措施

为了在不浪费空间的情况下尽可能的优化散列表的性能，我们的初始的桶数就要进行估算，但是事实上我们没法估算…。在java标准类库中采用了默认值为16的桶数。
除此之外，如果我们在使用的过程中，散列表过于满我们就需要对散列表进行再散列。再散列的方法很简单，把2的幂数加一，就是以32为桶数重新创建一个散列表，将原来各个桶中元素全部重新计算。那么我们在什么时候需要再散列呢？在散列表中存在一个装填因子，默认它的值为0.75。也就是说，如果原来的散列表被装满了75%以上时，这个散列表将会被再散列。

3.HashSet

package Collection;import java.util.HashSet;import java.util.Set;/**
 * 
 * @author QuinnNorris
 * 散列集HashSet,要理解存放方法,实际应用中无特别之处
 */public class HashSetE {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        Set<String> hs = new HashSet<>();
        hs.add("master");

        Set<String> sub_hs = new HashSet<>();
        sub_hs.add("sub");

        hs.addAll(sub_hs);//将另一个集合添加进来

        System.out.println(hs);//输出 [sub, master]
    }

}

散列集HashSet，要理解存放方法，实际应用中无特别之处。如果不需要索引，可用这种集合存放元素。

（六）  树集 TreeSet

TreeSet和HashSet很像，但是TreeSet却是一种有序集合。
正如其名，树集是一种树，它将插入这个集合的每个元素都按照一定的规律来排序比较，最后在循环输出的时候，树集输出的内容是有一定顺序的。也正是因为这个原因，插入树集的元素是必须能比较的，详细的说，所有插入树集的元素都要实现Comparable接口，否则会报错，这也是能比较的一个前提。

1.Comparable接口

我们已经知道，这个接口是插入树集前必须要实现的。Comparable接口定义了一个方法：

public interface Comparable<T>
{    int compareTo(T other);
}

compareTo方法返回的是一个int类型的数字，如果这个数字大于0，则说明排序时对象在参数之前，反之在参数之后。在集合中不会出现等于0的情况，毕竟集合是具有单一性，不能一个元素重复存在。

2.自定义Comparator接口

毕竟我们写的类不会自己附带一个Comparable接口的实现，那么很多时候，我们需要披挂上阵自己来定义比较的方法。我们可以创建一个Comparator实现类，在类中实现compare方法。请注意，我们手动实现的接口是Comparator而不是Comparable。更好的做法是我们将这个自定的类作为一个参数传入TreeSet的初始化语句中。

ItemComparator comp = new ItemComparator();
//ItemComparator是自己写的Comparable的实现类Set<String> ts = new TreeSet<String>(comp);
//将实例comp作为参数传入，TreeSet获得比较方法

3.匿名内部类

上面的自定义方法固然好，但是那并不是最简洁的写法，在这种情况下，匿名内部类真的起到了非常好的效果。只要你知道这里的参数是一个实现了compare方法的类对象，你就不会因为内部类的写法而感到很难读懂。

Set<Tree> ts = new TreeSet<Tree>(new 
    Comparator<Tree>(){        
    public int compare(Tree a,Tree b){            
    return a.index-b.index;
        }
    });

Tree是我们自己定义的一个类，自然没有Comparable接口的实现。所以我们在这里实现一下Comparator，采用的是匿名内部类的方法。事实上，Comparator接口还有equals方法，但是一般的情况下我们并不用去管它。

4.TreeSet实现的其他接口

TreeSet本身没有什么更多的便捷方法，但是它实现了很多接口，我们既然要看就看得透彻一些，来把这些接口也学习一下。

SortedSet<String> ts = new TreeSet<>();
//SortedSet接口Comparator<? super E> comparator()
// 返回对此 set 中的元素进行排序的比较器。如果此 set 使用其元素的自然顺序，则返回 null。E first()
//返回此 set 中当前第一个（最低）元素。 E last()
//返回此 set 中当前最后一个（最高）元素。 
NavigableSet<String> ts = new TreeSet<>();
//NavigableSet接口ceiling(E e) 
//返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。 Iterator<E> descendingIterator() 
//以降序返回在此 set 的元素上进行迭代的迭代器。 

 E floor(E e) 
//返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。 

 E higher(E e) 
//返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。 

 Iterator<E> iterator() 
//以升序返回在此 set 的元素上进行迭代的迭代器。 

 E lower(E e) 
//返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。 

 E pollFirst() 
//获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。 

 E pollLast() 
//获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

实际上，NavigableSet实现了SortedSet，如果想要使用上面的方法用NaviagableSet引用即可。

（七）  双端队列 ArrayDeque

顾名思义，有两个端头的队列就叫做双端队列，而deque的含义也正是“double ended queue”。双端队列可以在两端进行增删元素操作，但是不能在队列中间添加元素。

在java类库中，Deque8742468051c85b06f0a0af9e3e506b5c实现了Queue接口，而ArrayDeque实现了Deque接口。

package Collection;import java.util.ArrayDeque;import java.util.Deque;/**
 * 
 * @author QuinnNorris
 * 双端队列ArrayDeque的基本操作
 */public class ArrayDequeE {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        Deque<String> ad = new ArrayDeque<>();//默认构造一个大小为16的双端队列

        ad.add("a");//将一个对象插入双端队列的末尾
        ad.addFirst("b");//将一个对象插入双端队列的头部
        ad.addLast("c");//将一个对象插入双端队列的末尾

        String first = ad.pollFirst();//获取并移除双端队列的第一个元素，pollLast()功能相反

        String second = ad.getLast();//获取双端队列的最后一个元素，getFrist()功能相反

    }
}

这个类的功能也很明确就是在头部尾部能够做文章，偶尔或许会用到吧。值得一提的是，因为这个实现类继承了很多队列的接口，所以ArrayDeque里面有很多功能相同的方法，我们看着用就可以，作用是差不多的。

（八）  优先级队列 PriorityQueue

在操作系统中，CPU要处理很多进程任务，有个管理这些进程的算法就叫做优先级队列算法。java中的优先级队列和这个很像。在优先级队列中，元素只要add进去就不用管了，因为这个队列就是一个堆（heap），实质上是一个AVL二叉树。在这个二叉树中他总是按照compareTo方法将元素排序，优先级低的放在前面。

package Collection;import java.util.PriorityQueue;import java.util.Queue;/**
 * 
 * @author QuinnNorris
 * 优先级队列PriorityQueue基本用法
 */public class PriorityQueueE {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        Queue<String> pq = new PriorityQueue<>();
        pq.add("a");
        pq.offer("b");//向优先级队列中添加一个对象，和add方法相同。
        pq.offer("c");

        String head = pq.peek();//获取此列表的头
        System.out.println(head);//输出： a

        System.out.println(pq);//输出：[a, b, c]

        pq.remove();//移除队列中优先级最小的元素,也就是第一个元素，也可用参数表示删除什么元素

        System.out.println(pq);//输出： [b, c]
    }

}

PriorityQueue的方法也是出奇的简单，只有几种特殊的方法，毕竟二叉树自己内部就进行了自动调整，不需要我们做太多。与TreeSet一样，我们也可以通过自己创建实现了Comaprator接口的类对象来控制排序的原则。在PriorityQueue中值得注意的是，如果remove方法没有参数，那么默认会删除根节点的元素（第一个元素）。

（九）  散列表 HashMap

1.映射表

有的时候，我们要查找一个元素，但是并不想根据它的索引数字来查找。更有意义的，我们想用除了数字之外的类似String，Double，或者其他对象来查找这个值，那么这就涉及到一对数据。在java和很多语言中都实现了这种数据结构，通过一对键值对（key-value对）来存放数据，这就是映射表。

2.散列表特性

散列表和散列集的特性是基本差不多的，都是通过桶来储存。和散列集区别的是，它是根据键的hashcode来进行分配，散列集就比较简单。值得一提的是，键和值都可以为null，HashMap不是同步的，在多线程并发的情况下需要更多的保护操作。

package Collection;import java.util.HashMap;import java.util.Map;/**
 * 
 * @author QuinnNorris
 * HashMap的基本操作
 */public class HashMapE {

    /**
     * @param args
     */
    public static void main(String[] args) {        // TODO Auto-generated method stub

        Map<String,String> hm = new HashMap<>();
        Map<String,String> hmc = new HashMap<>(20,0.8F);
        //可以有两个参数，第一个表示桶的个数，第二个表示装填因子

        hm.put("key", "value");//存放键值对

        hm.get("key");//获取参数键的对应值，如果没有这个键则返回null

        hm.containsKey("key");//返回布尔值true;表示包含这个键

        hm.containsValue("value");//返回布尔值true，表示包含这个键

        hm.remove("key");//根据键来移除键值对

    }

}

在HashMap中，可以根据key来获取value的值，但是如果要反向根据value来获取key的值时则需要用到其他的手法，这个实现方法我们等到以后再讨论。

（十）  树表 TreeMap

树表是java集合类库提供的第二种表，这种表的特点全写在名字上了，树+表。具体有以下这些特性：

  1. 树会根据Comparable类的compareTo方法作为默认比较器，将传入元素排序

  2. 可以自己实现Comaprator类的compare方法作为比较器，将对象传入参数中

  3. 比较的变量是键key不是值value

  4. 树表比散列表稍微慢一些，不会慢太多，在需要有序输出的时候要用树表

（十一）  总结

一万多字的内容概括的介绍了所有在集合类库常用的几种类。这些类实现的原理不同，功能不同，大概可以分成List、Map、Set三大种，除了Map是Map接口实现的，其他的都是Collection接口实现的，在下面我们可以继续看一些集合框架，看java是怎么把这些类组合在一起的。

当我们要处理一串数据的时候，相比较c++和c中的数组和指针，在Java中我们更为常用的是ArrayList、HashMap等集合数据结构。c语言对指针的支持成就了他的深度，而Java中多种多样的包装类成就了他的广度。在java中，我们一般将List、Map、Set等数据结构通归为集合数据结构，这些类都存在于集合类库中。

 以上就是java集合（一）—数据结构详解 的内容，更多相关内容请关注PHP中文网（www.php.cn）！


성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
이전 기사：Java 복사 메커니즘에 대한 자세한 설명다음 기사：Java 복사 메커니즘에 대한 자세한 설명

관련 기사

더보기