[자료구조]해쉬(Hash)

1. 정의

- 해시 함수란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다.
- 매핑 전 데이터 값을 key, 매핑 후 데이터 값을 hash value라 하고, 매핑하는 과정을 해싱이라고 한다.

2. 특징

1. HashMap

   • Key 값과 Value값을 하나의 쌍으로 묶어 저장하는 자료구조 형태이다.
   • Key 값과 Value값을 하나의 쌍으로 묶어 저장하기 때문에 검색과 저장이 빠르다
   • Key 값이 배열의 인덱스 개념으로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도는 O(1) 이다
   • Key 값은 고유한 값이어야 하기 때문에 Key값이 중복되면 데이터가 저장되지 않는다.
   • 순서가 고려되지 않는다.

2. HashSet

   • HashSet은 Set 인터페이스를 구현한 것으로 들어오는 객체 중, 중복된 객체를 허용하지 않는다.
   • 순서를 신경쓰지 않는다. 순서까지 고려할때에는 TreeSet 또는 LinkedHashSet 사용권장
   • add(Object o) 메서드는 set에 데이터를 추가할 때 사용하는데, 정상적으로 추가되면 True를, 이미 존재하는 객체라면 False를 반환한다.

3. 사용방법

//HashMap 선언
HashMap<String,String> map1 = new HashMap<String,String>();//HashMap생성
HashMap<String,String> map2 = new HashMap<>();//new에서 타입 파라미터 생략가능
HashMap<String,String> map3 = new HashMap<>(map1);//map1의 모든 값을 가진 HashMap생성
HashMap<String,String> map4 = new HashMap<>(10);//초기 용량(capacity)지정
HashMap<String,String> map5 = new HashMap<>(10, 0.7f);//초기 capacity,load factor지정
HashMap<String,String> map6 = new HashMap<String,String>(){{//초기값 지정
    put("a","b");
}};


//HashMap 추가
HashMap<Integer,String> map = new HashMap<>();//new에서 타입 파라미터 생략가능
map.put(1,"사과"); //값 추가
map.put(2,"바나나");
map.put(3,"포도");

//HashMap 삭제
HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"사과");
    put(2,"바나나");
    put(3,"포도");
}};
map.remove(1); //key값 1 제거
map.clear(); //모든 값 제거

//HashMap 삭제
HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"사과");
    put(2,"바나나");
    put(3,"포도");
}};
		
System.out.println(map); //전체 출력 : {1=사과, 2=바나나, 3=포도}
System.out.println(map.get(1));//key값 1의 value얻기 : 사과
		
//entrySet() 활용
for (Entry<Integer, String> entry : map.entrySet()) {
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

//KeySet() 활용
for(Integer i : map.keySet()){ //저장된 key값 확인
    System.out.println("[Key]:" + i + " [Value]:" + map.get(i));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

//Iterator 사용
HashMap<Integer,String> map = new HashMap<Integer,String>(){{//초기값 지정
    put(1,"사과");
    put(2,"바나나");
    put(3,"포도");
}};
		
//entrySet().iterator()
Iterator<Entry<Integer, String>> entries = map.entrySet().iterator();
while(entries.hasNext()){
    Map.Entry<Integer, String> entry = entries.next();
    System.out.println("[Key]:" + entry.getKey() + " [Value]:" +  entry.getValue());
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도
		
//keySet().iterator()
Iterator<Integer> keys = map.keySet().iterator();
while(keys.hasNext()){
    int key = keys.next();
    System.out.println("[Key]:" + key + " [Value]:" +  map.get(key));
}
//[Key]:1 [Value]:사과
//[Key]:2 [Value]:바나나
//[Key]:3 [Value]:포도

4. 사용 예시

- 학생의 점수를 조회할 경우 (ex, 학생 이름, 점수)

- 회원 검색할 경우

- 관리해야 할 데이터가 많고 주로 검색을 많이 할 경우에 적합함

 

5. 기타

1. HashMap 추가 설명

- HashMap은 해시 함수를 통해 '키'와 '값'이 저장되는 위치가 결정된다

- 사용자는 그 위치를 알 수 없고, 삽입되는 순서와 들어 있는 위치 또한 상관없다.