데이터 구조: ArrayList, Vector, LinkedList 와 HashMap, HashTable, LinkedHashMap, TreeMap

1. ArrayList, Vector, LinkedList ArrayList 와 Vector 는 배열 방식 으로 데 이 터 를 저장 합 니 다. 이 배열 요 소 는 실제 저 장 된 데이터 보다 많 기 때문에 요 소 를 추가 하고 삽입 할 수 있 습 니 다. 이들 은 직접 번호 색인 요 소 를 허용 하지만 데 이 터 를 삽입 할 때 배열 요소 이동 등 메모리 작업 으로 설계 해 야 하기 때문에 색인 데이터 가 빠 르 고 삽입 데이터 가 느 립 니 다.Vector 는 synchronized 방법 (예 를 들 어 add, insert, remove, set, equals, hashcode 등) 을 사 용 했 기 때문에 라인 이 안전 하고 성능 이 ArrayList 보다 떨어진다.
LinkedList 는 양 방향 링크 를 사용 하여 저장 을 실현 합 니 다. 번호 색인 데 이 터 를 앞 뒤로 옮 겨 다 녀 야 하지만 데 이 터 를 삽입 할 때 이 항목 의 앞 뒤 항목 만 기록 하면 되 기 때문에 삽입 속도 가 빠 릅 니 다!LinkedList 양 방향 링크 는 first 에서 last (처음부터 끝까지) 까지 차례대로 옮 겨 다 닐 수도 있 고 last 에서 first (끝 에서 끝까지) 까지 옮 겨 다 닐 수도 있 지만 수미 에는 구성 고리 가 없고 양 방향 순환 링크 (주의 구분) 와 다 릅 니 다.
Array List 와 LinkedList 의 대체적인 차이 점:
    1. ArrayList 는 동적 배열 을 바탕 으로 하 는 데이터 구 조 를 실현 하고 LinkedList 는 링크 를 바탕 으로 하 는 데이터 구 조 를 실현 한다.
    2. 랜 덤 액세스 get 과 set 에 대해 Array List 는 LinkedList 보다 낫다 고 생각 합 니 다. LinkedList 는 지침 을 이동 해 야 하기 때 문 입 니 다.
    3. 추가 및 삭제 작업 add 와 remove 에 대해 서 는 linedList 가 우세 합 니 다. ArrayList 가 데 이 터 를 이동 해 야 하기 때 문 입 니 다.
    
Array List 와 LinkedList 는 성능 에 있어 각각 장단 점 이 있 고 각자 적용 되 는 부분 이 있 습 니 다. 전체적으로 다음 과 같이 설명 할 수 있 습 니 다.
1. Array List 와 LinkedList 의 경우 목록 끝 에 하나의 요 소 를 추가 하 는 데 쓰 이 는 비용 은 모두 고정 되 어 있 습 니 다.Array List 의 경우 내부 배열 에 하 나 를 추가 하고 추 가 된 요 소 를 가리 키 며 가끔 배열 을 다시 분배 할 수 있 습 니 다.링크 드 리스트 에 있어 서 이 비용 은 통일 적 이 고 내부 Entry 대상 을 배정 합 니 다.
2. Array List 의 중간 에 원 소 를 삽입 하거나 삭제 하 는 것 은 이 목록 에 남 은 요소 가 이동 하 는 것 을 의미 합 니 다.링크 드 리스트 의 중간 에 요 소 를 삽입 하거나 삭제 하 는 비용 은 고정 되 어 있 습 니 다.
3. LinkedList 는 효율 적 인 무 작위 요소 접근 을 지원 하지 않 습 니 다.
4. ArrayList 의 공간 낭 비 는 주로 list 목록 의 끝 에 일정한 용량 공간 을 남 겨 두 는 데 나타 나 고 LinkedList 의 공간 소 비 는 모든 요소 가 상당 한 공간 을 소모 해 야 한 다 는 데 나타난다.
이렇게 말 할 수 있 습 니 다. 작업 이 앞 이나 중간 이 아 닌 데이터 뒤에 데 이 터 를 추가 하고 그 중의 요 소 를 무 작위 로 방문 해 야 할 때 Array List 를 사용 하면 좋 은 성능 을 제공 합 니 다.데이터 의 앞 이나 중간 에 데 이 터 를 추가 하거나 삭제 하고 그 요소 에 순서대로 접근 할 때 LinkedList 를 사용 해 야 합 니 다.
2. HashMap, HashTable, LinkedHashMap 과 TreeMap Java 는 데이터 구조 에서 의 맵 으로 인터페이스 java. util. Map 을 정 의 했 습 니 다. 이 는 네 가지 실현 유형 이 있 는데 그것 이 바로 HashMap, HashTable, LinkedHashMap 과 TreeMap 입 니 다.
Map 은 키 (key) 값 (value) 을 저장 하 는 데 사용 되 며, 키 에 따라 값 을 얻 기 때문에 키 는 중복 되 지 않 지만, 값 이 중복 되 는 것 을 허용 합 니 다.Map 인터페이스의 해시 표 와 링크 목록 이 실현 되 며 예측 가능 한 교체 순서 가 있 습 니 다.이 실현 은 HashMap 과 다른 점 은 후자 가 모든 항목 에서 실행 되 는 이중 링크 목록 을 유지 하고 있다 는 점 이다.이 링크 목록 은 교체 순 서 를 정의 합 니 다. 이 교체 순 서 는 보통 맵 에 키 를 삽입 하 는 순서 (삽입 순서) 입 니 다.맵 에 키 를 다시 삽입 하면 삽입 순서 가 영향 을 받 지 않 습 니 다.(m. put (k, v) 를 호출 하기 전에 m. containKey (k) 가 true 로 돌아 오 면 호출 할 때 키 k 를 맵 m 에 다시 삽입 합 니 다.)
HashMap 은 키 의 HashCode 값 에 따라 데 이 터 를 저장 하고 키 에 따라 값 을 직접 얻 을 수 있 으 며 빠 른 접근 속 도 를 가진다.HashMap 은 최대 한 개의 기록 키 만 Null 로 허용 합 니 다.여러 개의 기록 값 을 Null 로 허용 하기;HashMap 은 스 레 드 의 동기 화 를 지원 하지 않 습 니 다. 즉, 언제든지 여러 스 레 드 가 동시에 HashMap 을 쓸 수 있 습 니 다.데이터 가 일치 하지 않 을 수 있 습 니 다.동기 화가 필요 하 다 면 Collections 의 synchronizedMap 방법 으로 HashMap 을 동기 화 할 수 있 습 니 다.
Hashtable 은 HashMap 과 유사 합 니 다. Dictionary 류 에서 계승 합 니 다. 다른 것 은 기 록 된 키 나 값 이 비어 있 는 것 을 허용 하지 않 습 니 다.이것 은 스 레 드 의 동기 화 를 지원 합 니 다. 즉, 어느 순간 에 하나의 스 레 드 만 Hashtable 을 쓸 수 있 기 때문에 Hashtable 은 기록 할 때 느 립 니 다.
링크 드 HashMap 도 HashMap 이지 만 내부 에 양 방향 링크 를 유지 하여 순 서 를 유지 할 수 있 습 니 다.링크 드 하 쉬 맵 은 하 쉬 맵 보다 하나의 링크 가 더 많은 구조 입 니 다.HashMap 에 비해 LinkedHashMap 은 이중 링크 를 가 진 HashMap 을 유지 합 니 다. LinkedHashMap 은 두 가지 정렬 을 지원 합 니 다. 하 나 는 삽입 정렬 이 고 하 나 는 정렬 을 사용 합 니 다. 하 나 는 정렬 을 사용 합 니 다. 최근 에 사용 한 것 은 M1 M2 M3 M4 입 니 다. M3 를 사용 한 후에 M1 M2 M4 M3 입 니 다. LinkedHashMap 출력 할 때 그 요 소 는 순서 가 있 고 HashMap 출력 할 때 무 작위 입 니 다.맵 맵 맵 이 복잡 하고 효율 적 이 라면 링크 드 HashMap 을 사용 하 는 것 이 좋 습 니 다. 그러나 다 중 스 레 드 를 방문 하면 동기 화 되 지 않 을 수 있 으 므 로 Collections. synchronizedMap 으로 포장 하여 동기 화 를 실현 해 야 합 니 다.
TreeMap 은 순 서 를 유지 할 수 있 을 뿐만 아니 라 정렬 에 도 사용 할 수 있 습 니 다. (TreeMap 은 저 장 된 기록 을 키 에 따라 정렬 할 수 있 습 니 다. 기본 값 은 오름차 순 으로 정렬 할 수도 있 고 정렬 된 비교 기 를 지정 할 수도 있 습 니 다.)TreeMap 은 SortMap 인 터 페 이 스 를 실현 합 니 다. 저 장 된 기록 을 키 에 따라 정렬 할 수 있 습 니 다. 기본 값 은 버튼 값 의 오름차 순 으로 정렬 할 수도 있 고 정렬 된 비교 기 를 지정 할 수도 있 습 니 다. Iterator 로 TreeMap 을 옮 겨 다 닐 때 얻 은 기록 은 정렬 된 것 입 니 다.TreeMap 의 키 와 값 이 비어 있 으 면 안 됩 니 다.
일반적인 상황 에서 우리 가 가장 많이 사용 하 는 것 은 HashMap 이다. Map 에 요 소 를 삽입 하고 삭제 하 며 포 지 셔 닝 하 는 것 이 가장 좋 은 선택 이다.하지만 자 연 스 러 운 순서 나 사용자 정의 순서 로 키 를 옮 겨 다 니 려 면 트 리 맵 이 좋 습 니 다.출력 순서 가 입력 과 같 아야 한다 면 링크 드 HashMap 으로 이 루어 질 수 있 고 읽 기 순서 로 배열 할 수 있 습 니 다.링크 드 하 쉬 맵 은 기록 의 삽입 순 서 를 저장 합 니 다. Iterator 로 링크 드 하 쉬 맵 을 옮 겨 다 닐 때 먼저 받 은 기록 은 반드시 먼저 삽 입 된 것 입 니 다. 옮 겨 다 닐 때 하 쉬 맵 보다 느 리 고 하 쉬 맵 의 모든 특성 이 있 습 니 다.
Collator 클래스 는 언어 환경 을 구분 하 는 String 비 교 를 수행 합 니 다.이 를 사용 하면 자연 언어 텍스트 에 검색 과 정렬 루틴 을 구축 할 수 있 습 니 다.
Collator 는 추상 적 인 기본 클래스 로 String 을 한 번 비교 하면 compare 방법 이 가장 좋 은 성능 을 제공 할 수 있 습 니 다.그러나 String 목록 을 정렬 할 때 는 각 String 을 여러 번 비교 해 야 합 니 다.
이런 상황 에서 CollationKey 는 더 좋 은 성능 을 제공 할 수 있다.CollationKey 클래스 는 하나의 String 을 다른 CollationKey 와 비트 별로 비교 할 수 있 는 일련의 비트 로 변환 합 니 다.
CollationKey 는 Collator 대상 이 지정 한 String 에 의 해 만 들 어 졌 습 니 다.
CollationKey 를 직접 만 들 수 없습니다.Collator. getCollationKey 를 호출 하여 생 성 합 니 다.
같은 Collator 대상 이 생 성 한 CollationKey 만 비교 할 수 있 습 니 다.
CollationKey 는 특정 Collator 대상 규칙 을 준수 하 는 String 을 뜻한다.
두 개의 CollationKey 를 비교 하면 그들 이 표시 하 는 String 의 상대 순 서 를 되 돌려 줍 니 다.
CollationKey 를 사용 하면 String 이 Collator. compare 를 사용 하 는 것 보다 빠 릅 니 다.
따라서 String 을 여러 번 비교 해 야 할 때 (예 를 들 어 하나의 String 목록 을 정렬 하 는 것),
CollationKey 를 사용 하면 더욱 효율 적 입 니 다.
지 도 를 옮 겨 다 니 는 방법 은 두 가지 가 있 습 니 다.
 (1) map 의 keyset () 방법 은 키 의 집합 을 얻 고 키 집합 iterator 방법 으로 키 의 교체 기 를 호출 하여 맵 의 키 를 교체 적 으로 꺼 내 get 방법 으로 키 에 대응 하 는 값 을 얻 으 면 맵 의 옮 겨 다 니 기 를 완성 합 니 다.코드 는 다음 과 같다.

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

 (2) Map 의 entry Set 방법 으로 Map 에 기 록 된 집합 을 얻 습 니 다. 모든 대상 은 Map. Entry 대상 입 니 다. getKey 방법 으로 기 록 된 키 를 얻 고 getValue 방법 으로 기 록 된 값 을 얻 습 니 다.코드 는 다음 과 같다.
       

 //         Map   Map.Entry
         Map.Entry entry = null;
         it = map.entrySet().iterator();
         while (it.hasNext()){
            //  Map.Entry      
            entry = (Map.Entry)it.next();
            //  entry          
            //System.out.println("key: " + entry.getKey() + "; value: " + entry.getValue());