다중 사용 및 다중 학습을 위한 Java의 Set, List 및 Map에 대한 자세한 설명-java지도 시간-php.cn

오랫동안 코드에서 더 자주 사용되는 데이터 목록은 주로 List이고, 모두 ArrayList이면 충분하다고 생각합니다. ArrayList는 동적 배열을 구현하는 데 사용되는 패키징 도구 클래스입니다. 이 방법을 사용하면 코드를 작성할 때 끌어오고 반복할 수 있어 매우 편리합니다.

언제부터 HashMap, HashSet 같은 툴 클래스가 코드에 자주 등장했는지는 모르겠습니다. HashMap이 더 많다고 해야되나, 전형적인 면접질문이라 좀 더 자주 봐야겠습니다. 처음 사용하시면 간단히 키-값 대응표로 이해하시면 됩니다. 키를 이용하여 데이터를 찾는 것이 더 편리합니다. 더 깊이 이해한 후에

이 부분에는 여전히 약간의 미스터리가 있다는 것을 발견했습니다. 특히 새 버전의 JDK가 HashMap을 트리로 변경한 후에는 코드가 약간 복잡해졌습니다.

처음에는 Set이 덜 사용되었습니다. 우연히 코드에서 TreeSet을 발견하고 이 클래스를 원활하게 사용할 수 있다는 것을 알게 되었고, 이 클래스도 좋은 도구라는 것을 천천히 알게 되었습니다.

코드를 많이 작성하다 보니 기본의 중요성을 느끼게 되어서, 컬렉션에 대한 지식을 간략하게 정리하기 위해 여기에 짧은 글을 써보겠습니다.

자, 간단히 정리해 보겠습니다.

•List: 목록이며 배열과 연결 목록의 기능을 지원하며 일반적으로 선형입니다.
•Map: 매핑입니다. 테이블, 저장되는 것은 키와 값의 대응 관계
•Set: 집합을 의미하며 주로 데이터 중복 제거 및 정렬에 사용됩니다

List를 살펴보겠습니다

리스트는 배열의 경우 ArrayList, 연결리스트의 경우 LinkedList 등 선형 데이터를 저장하는 데 사용되는 창입니다.

ArrayList

배열 목록이지만 자동 확장 기능을 제공하고 List 인터페이스를 구현하여 인터페이스에 선언된 메소드를 통해 외부 작업에 접근하므로 안전하고 편리합니다. .

ArrayList의 핵심은 자동 확장입니다. 객체가 초기화되면 초기 용량이나 기본 용량을 설정할 수 있습니다. 배열 크기가 특별히 명확하지 않은 경우 초기 크기를 지정할 필요가 없습니다. 명확하면 크기를 지정하여 동적 확장으로 인한 지연을 줄일 수 있습니다. 말하자면, 확장이 어떻게 달성되는지 이야기해 보겠습니다.

private void grow(int minCapacity) {
 
    // overflow-conscious code
 
    int oldCapacity = elementData.length;
 
    int newCapacity = oldCapacity + (oldCapacity >> 1);
 
    if (newCapacity - minCapacity < 0)
 
      newCapacity = minCapacity;
 
    if (newCapacity - MAX_ARRAY_SIZE > 0)
 
      newCapacity = hugeCapacity(minCapacity);
 
    // minCapacity is usually close to size, so this is a win:
 
    elementData = Arrays.copyOf(elementData, newCapacity);
 
  }

로그인 후 복사

grow는 ArrayList가 요소를 추가하거나 몇 가지 간단한 검사를 수행할 때 트리거되는 메서드입니다. 주요 프로세스:

1. 배열의 길이를 가져와서 오른쪽으로 이동합니다. 이는 oldCapacity/2와 동일하며 새 길이를 가져옵니다.

이 길이가 최소값보다 작은 경우. 그런 다음 최소 easy를 사용하세요

3. 최대 easy보다 큰 경우 최대값을 사용합니다. 여기서는 hugeCapacity 메서드가 호출되며 주로 minCapacity가 MAX_ARRAY_SIZE보다 큰 경우에 사용됩니다. MAX_ARRAY_SIZE는 Integer.MAX_VALUE를 취하고 그렇지 않으면 MAX_ARRAY_SIZE를 취합니다. 흥미로운 점은 MAX_ARRAY_SIZE가 Integer.MAX_VALUE - 8을 취한다는 것입니다.

4. 기존 숫자를 새 배열로 복사하는 복사 방법입니다.

이러한 복사 프로세스로 인해 배열이 상대적으로 큰 경우 확장이 항상 트리거되면 물론 지연이 발생합니다. 따라서 최대값이 처음부터 알려져 있고 이 값까지 쉽게 증가할 수 있는 경우 초기화 시작 시 크기를 지정하면 어느 정도 효과가 있습니다.

LinkedList

연결된 목록을 위한 도구 클래스입니다. 연결 목록의 장점은 추가 및 삭제 속도가 빠르지만 검색 속도가 느려진다는 것입니다.

코드에 관해서는 특별한 것이 없는 것 같습니다. 물론 Java에서는 Node 자체가 이전 개체를 가리키는 데 사용됩니다. 노드와 다음 노드는 다음과 같습니다. 연결 목록의 구조:

private static class Node<E> {
 
   E item;
 
   Node<E> next;
 
   Node<E> prev;
 
 
 
   Node(Node<E> prev, E element, Node<E> next) {
 
     this.item = element;
 
     this.next = next;
 
     this.prev = prev;
 
   }
 
 }

로그인 후 복사

그런 다음 두 개의 노드를 사용하여 머리와 꼬리를 가리킵니다.

/**
 
   * Pointer to first node.
 
   * Invariant: (first == null && last == null) ||
 
   *      (first.prev == null && first.item != null)
 
   */
 
  transient Node<E> first;
 
  
 
  /**
 
   * Pointer to last node.
 
   * Invariant: (first == null && last == null) ||
 
   *      (last.next == null && last.item != null)
 
   */
 
  transient Node<E> last;

로그인 후 복사

추가 작업을 살펴보세요. :

/**
 
   * Links e as last element.
 
   */
 
  void linkLast(E e) {
 
    final Node<E> l = last;
 
    final Node<E> newNode = new Node<>(l, e, null);
 
    last = newNode;
 
    if (l == null)
 
      first = newNode;
 
    else
 
      l.next = newNode;
 
    size++;
 
    modCount++;
 
  }

로그인 후 복사

과거는 다음과 같습니다.

1. 마지막 노드를 가져와서 l에 넣습니다.

2. 새 노드를 만들고 이 노드에 데이터를 가져옵니다. 생성 프로세스는 새 노드의 이전 항목을 l 로 지정하여 체인을 연결합니다

3. 그런 다음 마지막으로 이 새 노드를 지정합니다

. 그런 다음 l이 null인지 확인합니다. null이면 빈 연결 목록이고 새 노드가 첫 번째 요소이므로 먼저 newNode

5를 가리켜야 합니다. 비어 있지 않으면 l 옆에 newNode<를 가리켜야 합니다. 🎜>

6. 누적 카운터

삭제 작업도 이런 Node입니다. 앞뒤 Node가 이동 작업을 가리킵니다.

Map을 살펴보겠습니다

Map은 키와 값 사이의 매핑 테이블을 생성하는 애플리케이션입니다. 주요 구현 클래스는 HashMap, HashTable, TreeMap입니다.

HashMap과 HashTable

키-값 매핑을 위해 해시 알고리즘을 사용하는 것이 HashMap입니다. HashTable은 동기화 기능이 있는 스레드 안전 클래스입니다. 원리도 비슷하며 둘 다 버킷 + 체인 조합을 통해 구현됩니다. 버킷은 키를 저장하는 데 사용되며, 해시 충돌로 인해 값을 연결 목록에 저장해야 합니다.

•버킷의 의의는 해시 계산을 통해 한 번에 찾을 수 있는 높은 효율성에 있습니다

•연결된 목록의 의의는 중복된 해싱된 데이터에 접근하는 데 있습니다

구체적인 원리 이전에 "스터디 노트"에 작성되었습니다 : Hashtable 및 HashMap》

JDK1.8의 HashMap이 저장 구조를 변경하고 레드-블랙 트리 구조를 채택한 것뿐입니다. 이렇게 하면 연결 목록의 문제가 해결될 수 있습니다. 검색 효율성이요? 자세한 연구는 없습니다.

트리맵

看过TreeMap的代码后发现还是使用的树结构，红黑树。由于红黑树是有序的，所以自然带排序功能。当然也可通过comparator来指定比较方法来实现特定的排序。

因为采用了树结构存储那么添加和删除数据时会麻烦一些，看一下put的代码：

public V put(K key, V value) {
 
    Entry<K,V> t = root;
 
    if (t == null) {
 
      compare(key, key); // type (and possibly null) check
 
  
 
      root = new Entry<>(key, value, null);
 
      size = 1;
 
      modCount++;
 
      return null;
 
    }
 
    int cmp;
 
    Entry<K,V> parent;
 
    // split comparator and comparable paths
 
    Comparator<? super K> cpr = comparator;
 
    if (cpr != null) {
 
      do {
 
        parent = t;
 
        cmp = cpr.compare(key, t.key);
 
        if (cmp < 0)
 
          t = t.left;
 
        else if (cmp > 0)
 
          t = t.right;
 
        else
 
          return t.setValue(value);
 
      } while (t != null);
 
    }
 
    else {
 
      if (key == null)
 
        throw new NullPointerException();
 
      @SuppressWarnings("unchecked")
 
        Comparable<? super K> k = (Comparable<? super K>) key;
 
      do {
 
        parent = t;
 
        cmp = k.compareTo(t.key);
 
        if (cmp < 0)
 
          t = t.left;
 
        else if (cmp > 0)
 
          t = t.right;
 
        else
 
          return t.setValue(value);
 
      } while (t != null);
 
    }
 
    Entry<K,V> e = new Entry<>(key, value, parent);
 
    if (cmp < 0)
 
      parent.left = e;
 
    else
 
      parent.right = e;
 
    fixAfterInsertion(e);
 
    size++;
 
    modCount++;
 
    return null;
 
  }

로그인 후 복사

1、先是检查根节点是否存在，不存在说明是第一条数据，直接作为树的根

2、判断是否存在比较器，如果存在则使用比较器进行查找数据的存放位置，如果比较器返回结果小于0取左，大于0取右，否则直接替换当前节点的值

3、如果不存在比较器则key直接与节点的key比较，比较和前面方法一样

4、接下来就是在找到的parent上创建一个子节点，并放入左或者右子节点中

5、fixAfterInsertion是对节点进行着色

6、累加器处理

在remove操作时也会有点麻烦，除了删除数据外，还要重新平衡一下红黑树。

另外，TreeMap实现了NavigableMap接口，所以也提供了对数据集合的一些返回操作。

最后看看Set

Set主要是两类应用：HashSet和TreeSet。

HashSet

字面意思很明确，使用了Hash的集合。这种集合的特点就是使用Hash算法存数据，所以数据不重复，存取都相对较快。怎么做到的呢？

public boolean add(E e) {
 
    return map.put(e, PRESENT)==null;
 
  }

로그인 후 복사

原来是存在一个map对象中，再看map是个啥？

private transient HashMap<E,Object> map;

로그인 후 복사

是个HashMap，了解HashMap的就明白，这样的数据是不会重复的。因为存入时是鼗对象本身作为Key来存的，所以在HashMap中只会存在一份。

了解了这点其他的东西就非常明白了。

TreeSet

这个集合是用于对集合进行排序的，也就是除了带有排重的能力外，还可以自带排序功能。只不过看了TreeSet的代码发现，其就是在TreeMap的基础实现的。更准确的说应该是NavigableMap的派生类。默认不指定map情况下TreeSet是以TreeMap为基础的。

public TreeSet() {
 
    this(new TreeMap<E,Object>());
 
  }

로그인 후 복사

所以，这里可能更关注的是TreeSet是如何排重呢？看一下add的方法吧：

public boolean add(E e) {
 
    return m.put(e, PRESENT)==null;
 
  }

로그인 후 복사

和HashSet有点类似，都是基于Map的特性来实现排重。确实简单而且有效。

以上就是小编为大家带来的多用多学之Java中的Set,List,Map详解全部内容了，希望大家多多支持PHP中文网~

更多多用多学之Java中的Set,List,Map详解相关文章请关注PHP中文网！