hashSet,TreeSet,HashMap,Hashtable,Collections

해싱과 해시함수

 

해시함수(hash function)를 이용해 저장하고 검색하는 기법입니다.

 

 

해시 테이블(Hash Table)

---

 

 

 

 

 

 

 

 

 

 

hashSet

중복된 요소를 저장하지 않습니다.

 

저장순서를 유지하고자 한다면 LinkedHashSet을 사용해야 합니다.

 

 

class Ex11_9 {
    public static void main(String[] args) {
        Object[] objArr = {"1",new Integer(1),"2","2","3","3","4","4","4"};
        Set set = new HashSet();

        for(int i=0; i < objArr.length; i++) {
            set.add(objArr[i]);    // HashSet에 objArr의 요소들을 저장한다.
        }
        // HashSet에 저장된 요소들을 출력한다.
        System.out.println(set);

        // HashSet에 저장된 요소들을 출력한다.(Iterator이용)
        Iterator it = set.iterator();

        while(it.hasNext()) {
            System.out.println(it.next());
        }
    }

 

TreeSet

자료구조의 형태로 데이터를 저장하는 컬랙션 클래스입니다 이진검색 트리는 정렬, 검색, 범위검색에 높은 성능을 보이는

자료구조이며 TreeSet은 이전 검색 트리의 성능을 향상시킨 레드-블랙 트리로 구현되어 있습니다.

 

중복된 데이터의 저장을 허용하지 않으며 정렬된 위치에 저장하므로 저장순서를 유지하지 않아도 됩니다.

 

노드에 최대 2개의 노드를 연결할 수 있으며 루트라고 불리는 하나의 노드에서부터 시작해서 계속 확장해 나갈 수 있습니다.

 

 

 

class TreeNod {
        TreeNode left;//왼쪽 자식노드
        Object element;//객체를 저장하기 위한 참조변수
        TreeNode rigth;//오른쪽 자식노드
}

public class TreeSet1 {
    public static void main(String[] args) {
    Set set = new TreeSet();


    for (int i =0; set.size()<6 ; i++){
            int num = (int)(Math.random()*45) +1;
            set.add(num); //set.add(new Integer(num));
    }
        System.out.println(set);

    }

package Set.TreeSet;

import java.util.TreeSet;

public class TreeSet3 {
        public static void main(String[] args){
            TreeSet set = new TreeSet();
            int[] score = {80,95,50,35,45,65, 10, 100};

            for (int i=0; i<score.length; i++)
                set.add(new Integer(score[i])); //배열의 데이터를 treeset에 담기

            System.out.println("50보다 작은 값:" + set.headSet(50)); //50보다 작은값이 어떤것 인지 출력 //컴파일러가 new Integer()를 자동적으로 오토박싱 해준다.
            System.out.println("50보다 큰 값:" +set.tailSet(new Integer(50)));// 50보다 큰값이 어떤것 인지 출력
            System.out.println("40과 80사이의 값:" +set.subSet(40,80)); //40~80 사이에 있는 값을 출력 80 제외
        }

}

/*
    어떤 값을 기준으로  작은값은       headSet
    어떤 값을 기준으로     큰값       tailSet
특정값~특정값(특정값 마지막은 해당안됨)  subSet


*/

이진 검색 트리

왼쪽에는 부모노드의 값보다 작은 값   

오른쪽에는 큰 값의 자식노드를 저장하는 이진트리입니다.

왼쪽 자식노드의 값은 부모노드의 값보다 작고 오른쪽 자식 노드의 값은 부모 노드의 값보다 커야 합니다

노드의 추가 삭제에는 시간이 걸립니다(순차적으로 저장하지 않으므로)

검색과 정렬에 유리합니다

중복된 값을 저장하지 못합니다.

 

 

 

 

HashMap

키(key) 값(value)을 묶어서 하나의 데이터로 저장한다는 특징을 가지고 있습니다

해싱을 사용하기 때문에 많은 양의 데이터를 검색하는 데 있어서 아주 뛰어난 성능을 가지고 있습니다.

 

 

 

(중복x) 키(key)     컬렉션 내의 키 중에서 유일해야 합니다

(중복o) 값(value) 키와 달리 데이터의 중복을 허용합니다.

 

 

 

public static void main(String[] args){
    HashMap map = new HashMap();

    map.put("myId","1234");
    map.put("asdf","1111");
    map.put("asdf","1234"); //마지막 값으로 적용된다.

    Scanner s = new Scanner(System.in); //화면으로부터 라인단위로  입력받는다.


   while (true){ //비밀번호 일치할때 까지 무한 반복문
       System.out.println("id와 password 를 입력해주세요.");
       System.out.println("id:");
       String id = s.nextLine().trim();

       System.out.print("Password:");
       String password = s.nextLine().trim(); //trim 은 공백 제거 "  1 23   4  " => "1234"
       System.out.println();

       if (!map.containsKey(id)){ //아이디가 이 key중에 있는지 확인
           System.out.println("입력하신 id는 존재하지않습니다. 다시 입력해주세요");
       continue; //다시 while 첫번째로 돌아가기.
       }
       if (!(map.get(id)).equals(password)){
           System.out.println("비밀번호가 일치하지 않습니다. 다시 입력해주세요.");
       }else {
           System.out.println("id와 비밀번호가 일치합니다.");
           break;
       }
   } //while
} //main 의 끝

public static void main(String[]args){
    HashMap map = new HashMap();
    map.put("김자바", new Integer(90));
    map.put("김자바", new Integer(100));// 키값일 일치하기 때문에 새로운값으로 바뀐다.
    map.put("이자바", new Integer(100));
    map.put("강자바", new Integer(80));
    map.put("안자바", new Integer(90));

    Set set = map.entrySet(); //엔트리 셋으로 가져오면 키,벨류가 하나로 묶여서 반환한다.
    Iterator it = set.iterator();

    while (it.hasNext()){
        Map.Entry e = (Map.Entry)it.next();
        System.out.println("이름:" +e.getKey()+", 점수: "+e.getValue());

    }
set = map.keySet(); //이름만(Key)만 가져오고 싶을때
    System.out.println("참가자 명단: "+set);


    Collection values = map.values();//값들만 다 가져오는 것이 values
    it = values.iterator();

    int total = 0;

    while (it.hasNext()) {
        int i = (int)it.next();
        total += i; //가지고온 값들을 다 더하기.

    }
    System.out.println("총점 : " + total);
    System.out.println("평균 : " +(float)total/set.size()); //float를 안하면 정수로 나오기때문에 평균값이 정확하지 않을수 있다.
    System.out.println("최고점수 : " + Collections.max(values)); 
    System.out.println("최저점수 : " + Collections.min(values));


}

 

Collections

컬렉션과 관련된 메서드를 제공합니다 fill(),copy(),sort(),binarySearch() 등의 메서드는 두 클래스에 모두 포함되어 있으며 같은 기능을 합니다.

 

 

컬랙션의 동기화

 

멀티 스레드 프로그래밍에서는 하나의 객체를 여러 스레드가 동시에 접근할 수 있기 때문에 데이터의 일관성을 유지하기 위해서는 공유되는 객체에 동기화가 필요합니다.

 

 

static Collection synchronizedCollection(Collection c)
        static List synchronizedList (List list)
            static Set synchronizedSet (Set s)
                static Map synchronizedMap (Map m)
                    static SortedSet synchronizedSortedSet(SortedSet s)
                        static SortedMap synchronizedSortedMap(SortedMap m)
                            
                            List syncList =Collections.synchronizedList(new ArrayList(...));

 

 

변경불가 컬렉션 만들기

변경할 수 없게 읽기 전용으로 만듭니다

하나의 컬렉션을 공유하다 보면 데이터가 손상될 수 있는데 이를 방지하려고 사용합니다

 

static Collection unmodifiableCollection(Collection c)
        static List unmodifiableList (List list)
            static Set unmodifiableSet (Set s)
                static Map unmodifiableMap (Map m)
                    static SortedSet unmodifiableSortedSet(SortedSet s)
                        static SortedMap unmodifiableSortedMap(SortedMap m)
                            

 

싱글톤 컬렉션 만들기

 

단 하나의 객체만을 저장할 때 사용합니다.

 

static List singletonList(Object o)
static Set singleton(Object o)   //singletonSet 아님 
static Map singletonMap(Object o)