1. HashMap과 Hashtable
HashMap과 Hashtable의 관계는 Vector과 ArrayList과 같아서 Hashtable보다 새로운 버전인 HashMap을 사용할 것을 권한다. HashMap은 Map을 구현했으므로 앞에서 살펴본 Map의 특징, key와 value를 묶어서 하나의 데이터(entry)로 저장한다는 특징을 갖는다. 그리고 해싱(hashing)을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어 뛰어난 성능을 보인다.
HashMap은 Entry라는 내부 클래스를 정의하고, 다시 Entry 타입의 배열을 선언하고 있다. 키와 값은 별개의 값이 아니라 서로 관련된 값이기때문에 각각의 배열로 선언하기 보다는 하나의 클래스로 정의해서 하나의 배열로 다루는 것이 데이터의 무결성적인 측면에서 더 바람직하기 때문이다.
HashMap은 키와 값을 각각 Object 타입으로 저장한다. 따라서 어떠한 객체도 저장할 수 있지만 키는 주로 String 사용한다.
- Key : 컬렉션 내의 키 중에서 유일해야한다.
- Value : 키와 달리 데이터의 중복을 허용한다
키는 저장된 값을 찾는데 사용되는 것이기때문에 컬렉션 내에서 유일해야한다.
생성자/메서드 설명
메서드 | 설명 |
HashMap() | HashMap 객체를 생성 |
HashMap(int initialCapacity) | 지정된 값을 초기용량으로 하는 HashMap 객체 생성 (16, 0.75가 디폴트) |
HashMap(int initialCapacity, float doubleFactor) | 지정된 초기용량과 load factor의 HashMap객체를 생성 |
HashMap(Map m) | 지정된 Map의 모든 요소를 포함하는 HashMap을 생성 |
void clear() | HashMap에 저장된 모든 객체를 제거 |
Object clone() | 현재 HashMap을 복제해서 반환 |
boolean containsKey(Object key) | HashMap에 지정된 키가 포함되어있는지 알려준다. |
boolean containsValue(Object value) | HashMap에 지정된 값이 포함되어있는지 알려준다. |
Set entrySet() | HashMap에 저장된 키와 값을 엔트리의 형태로 set에 저장해 반환 |
Object get(Object key) | 지정된 키의 값을 반환. 못 찾으면 null 반환 |
Object getOrDefault(Object key, Object defaultValue) | 지정된 키의 값을 반환한다.키를 못찾으면 기본값으로 지정된 객체를 반환 |
boolean isEmpty() | HashMap이 비어있는지 알려준다. |
Set keySet() | HashMap에 저장된 모든 키가 저장된 set을 반환 |
Object put(Object key, Object value) | 지정된 키와 값을 HashMap에 저장 |
void putAll(Map m) | Map에 저장된 모든 요소를 HashMap에 저장 |
Object remove(Object key) | HashMap에 지정된 키로 값 제거 |
Object replace(Object key, Object value) | 지정된 키의 값을 지정된 객체로 대체 |
boolean replace(Object key, Object oldValue,newValue) | 지정된 키와 객체가(oldValue)가 모두 일치하는 경우에만 새로운 객체(newValue)로 대체 |
int size() | HashMap에 저장된 요소의 개수를 반환 |
Collection values() | HashMap에 저장된 모든 값을 컬렉션의 형태로 반환 |
- load factor : 부하율 혹은 적재율로 만약 0.75일떄 총 버킷의 75%에 달하는 데이터가 적재된다면 버킷을 늘린다.
//HashMap 객체 생성
HashMap<Object, Object> hm1 = new HashMap<>();
HashMap<Object, Object> hm2 = new HashMap<>(10);
HashMap<Object, Object> hm3 = new HashMap<>(10, 0.8F);
HashMap<Object, Object> hm4 = new HashMap<>(hm1);
- HashMap 예제 1 : id, 비밀번호
public class HashMapEx1 {
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.print("id :");
String id = s.nextLine().trim();
System.out.print("password :");
String password = s.nextLine().trim();
System.out.println();
if (!map.containsKey(id)) {
System.out.println("입력하신 id는 존재하지 않습니다.");
continue; //다시 처음부터
}
if (!map.get(id).equals(password)) {
System.out.println("비번이 일치하지 않습니다. 다시 입력해주세요 ");
} else {
System.out.println("일치합니다");
break;
}
}
}
}
값을 추가할때 asdf라는 키값이 이미 존재하기 때문에 기존의 값의 덮어씌어서 “asdf”에 연결된 값은 “1234”이다. 참고로 HashMap은 null을 허용하기 때문에 map.put(null, null)이 가능하다.
- HashMap 예제 2
public class HashMapEx2 {
public static void main(String[] args) {
HashMap map = new HashMap<>();
map.put("김자바",100);
map.put("이자바",100);
map.put("박자바",80);
map.put("안자바",90);
Set set = map.entrySet();//set으로 반환
System.out.println(set);
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를 set으로 반환
System.out.println("참가자 명단" + set);
Collection<Integer> values = map.values();//모든 value 를 set으로 반환
it = values.iterator();
int total =0;
while (it.hasNext()){
Integer i = (Integer) it.next();
total += i;
}
System.out.println("총점" +total);
System.out.println("평균" + total/set.size());
System.out.println("최고점수" + Collections.max(values));
System.out.println("최저점수" + Collections.min(values));
}
}
- HashMap 예제 3 : 전화번호부 만들기
public class HashMapEx3 {
static HashMap<String,HashMap<String,String>> phoneBook = new HashMap<>();
public static void main(String[] args) {
addPhoneNo("친구", "김자바", "1111-2222");
addPhoneNo("친구", "이자바", "1111-1111");
addPhoneNo("회사", "김파이썬", "1111-3333");
addPhoneNo("회사", "이파이썬", "1111-4444");
addPhoneNo("회사", "박파이썬", "1111-5555");
//출력
printList();
}
//그룹에 전화번호 추가하는 메서드
static void addPhoneNo(String groupName, String name, String tel){
addGroup(groupName);
HashMap<String,String> group = phoneBook.get(groupName);
group.put(tel, name); //이름 중복 가능성이 있으니 번호를 key로 저장
}
//그룹을 추가하는 메서드
static void addGroup(String groupName){
//해당 그룹이 없으면 추가
if(!phoneBook.containsKey(groupName)){
phoneBook.put(groupName, new HashMap<>());
}
}
static void printList(){
Set set= phoneBook.entrySet();
System.out.println(set);
Iterator it = set.iterator();
while(it.hasNext()){
Map.Entry e = (Map.Entry) it.next(); //entry는 하나의 쌍을 묶어서 데이터로 저장
Set subset = ((HashMap)e.getValue()).entrySet(); //entrySet은 HashMap메소드, entry 형태로 set애 저장해서 반환
Iterator subit = subset.iterator();
System.out.println(" * " + e.getKey() + "[" + subset.size() + "]"); //그룹
while (subit.hasNext()){
Map.Entry subE = (Map.Entry)subit.next(); //[이자바 : 1111-1111] 형태
String telNo = (String)subE.getKey();
String name = (String)subE.getValue();
System.out.println(name + " " + telNo);
}
}
}
}
- HashMap 예제 4
public class HashMapEx4 {
public static void main(String[] args) {
String[] data = {"A", "B", "C", "D", "A", "B", "B", "B", "B"};
HashMap map = new HashMap<>();
for (int i = 0; i < data.length; i++) {
if (map.containsKey(data[i])) {
Integer value = (Integer) map.get(data[i]);
map.put(data[i], value + 1);
} else {
map.put(data[i], 1);
}
}
Iterator it = map.entrySet().iterator(); //키와 값의 entry형태로 set에 저장해 반환
while (it.hasNext()) {
Map.Entry entry = (Map.Entry) it.next();
int value = ((Integer) entry.getValue()).intValue();
System.out.println(entry.getKey() + ":" + printBar('#', value) + " " + value);
}
}
public static String printBar(char ch, int value) {
char[] bar = new char[value];
for (int i = 0; i < bar.length; i++) {
bar[i] = ch;
}
return new String(bar);
}
}
해싱과 해시함수
해싱이란 해시함수(Hash Function)을 이용해 데이터를 해시테이블(hash table)에 저장하고 검색하는 기법을 말한다. 해시함수는 데이터가 저장되어 있는 곳을 알려주기 때문에 많은 데이터 중에서도 원하는 데이터를 빠르게 찾을 수 있다.
해싱을 구현한 클래스로는 HashSet, HashMap, Hashtable이 있는데 Hashtable은 컬렉션 프레임워크가 도입되면서 HashMap으로 대체되었기 때문에 사용하지 않기로 하자.
해싱에서 사용하는 자료구조는 배열과 링크드 리스트로 구성되어있다.
저장할 데이터의 키를 해시함수에 넣으면 배열의 한 요소를 얻게 되고, 다시 그 요소에 연결되어있는 링크드 리스트에 저장하게 된다.
위의 그림은 HashMap에 저장된 데이터를 찾는 과정이다. 79년생 환자의 주민번호를 키로 해시함수를 통해 7이라는 해시코드를 얻은 다음 배열의 7번째 요소에 저장된 링크드 리스트에서 원하는 데이터를 검색하는 과정이다.
- 검색하고자 하는 값의 키로 해시함수를 호출한다.
- 해시함수의 계산결과(해시코드)로 해당값이 저장되어 있는 링크드 리스트를 찾는다.
- 링크드리스트에서 검색한 키와 일치하는 데이터를 찾는다.
링크드 리스트는 검색에 불리한 자료구조이기때문에 (인덱스가 없어 모든 노드를 순차적으로 확인) 링크드 리스트의 크기가 커질수록 검색속도가 떨어지게 된다. 반면에 배열의 크기가 커져도 원하는 요소가 몇번째에 있는지만 알면 아래의 공식에 의해 빠르게 원하는 값을 찾을 수 있다.
- 배열의 인덱스가 n인 요소의 주소 = 배열의 시작주소 + type의 size * n
따라서 하나의 서랍(링크드리스트)에 많은 데이터가 저장되어있는 것보다 많은 서랍에 하나의 데이터만 저장되어 있는 형태가 빠른 검색 결과를 얻을 수 있다. (첫번째 이미지 참고) 따라서 서랍에 최소한의 데이터만 저장되려면 저장될 데이터의 크기를 고려해 HashMap의 크기를 적절하게 지정해야하고, 해시함수가 서로 다른 키에 대해 중복된 해시코드의 반환을 최소화 해야한다. 그래야 HashMap에서 더 빠른 검색시간을 얻을 수 있다.
그래서 해싱을 구현하는 과정에서 제일 중요한 것은 해시함수의 알고리즘이다. 위의 예시에서 사용된 해시함수의 알고리즘은 주어진 키 (주민번호)의 첫번째 문자를 뽑아서 정수로 반환하는 것이므로 아래 코드와 같다.
다만 알고리즘이 간단한 만큼 성능은 좋지 않아 서로 다른 키에 대해 중복된 해시코드를 반환하는 경우가 많다.
int hashFunction(String key){
return Integer.parseInt(key.substring(0,1));
}
실제로는 HashMap과 같이 Hashing을 구현한 컬렉션 클래스는 Object 클래스에 정의된 hashCode()를 해시함수로 사용한다. hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체한 결과가 서로 다르게 유일하다.
다만 String클래스의 경우 Object로 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다. 따라서 서로 다른 String 인스턴스일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출했을때 같은 해시코드를 얻는다.
출처 : 자바의 정석
'Java' 카테고리의 다른 글
[JAVA] 변수와 변수의 타입 (1) | 2023.12.07 |
---|---|
[JAVA] TreeMap (1) | 2023.12.07 |
[JAVA] TreeSet (0) | 2023.12.07 |
[Java] HashSet (0) | 2023.12.06 |
[Java] Stack과 Queue (1) | 2023.12.06 |