다중 사용 및 다중 학습을 위한 Java의 Set, List 및 Map에 대한 자세한 설명
- 高洛峰원래의
- 2017-01-19 10:45:151136검색
오랫동안 코드에서 더 자주 사용되는 데이터 목록은 주로 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가 이동 작업을 가리킵니다.•연결된 목록의 의의는 중복된 해싱된 데이터에 접근하는 데 있습니다
看过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实现了NavigableMapb77a8d9c3c319e50d4b02a976b347910接口，所以也提供了对数据集合的一些返回操作。
最后看看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中文网！