- 해시(Hash)
key와 Value가 한 쌍으로 존재한다, key값이 중복되지 않는다.
Value는 key로 매핑했을 때 나오는 값이다.
고정된 크기로 값을 바꾸는 함수나 알고리즘이다. 만들어진 값을 해시코드(값) 이라고 한다.
= 해시는 빠르게 찾기 위해서 사용한다. (= 빠른 검색 속도)
- 계산 속도가 빨라야 한다.
- 결괏값이 다양해야 한다.
해시 값을 빨리 만들 수 없다면 문제가 된다. 목차로만 찾고자 하는 다양한 내용을 찾을 수 없다.
- 해시 충돌(Hash Collision)
서로 다른 대상이 동일한 해시 값을 가지는 현상이다.
1) 분리 연결법
충돌이 발생하면 연결된 새로운 공간을 사용한다.
2) 개방 주소법
충돌이 발생하면 다른 해시코드를 사용한다.
- Hash Collection
1) HashMap
key의 중복을 피하기 위하여 해시를 사용하는 Map 자료구조이다.
null값을 삽입할 수 있다. 중복 Value는 허용한다.
put()메서드를 사용하여 데이터 삽입 key-value형태 한 쌍
HashSet보다 빠르다.
- 형태
key와 value형태
2) HashTable
HashMap과 거의 유사한 자료 구조, 동기화를 지원한다.
null값을 삽입할 수 없다.
3) HashSet
고유한 요소의 정렬되지 않는 컬렉션이다.
중복값이 허용되지 않는다. null값을 삽입할 수 있다. 일정한 시간 O(1)에 요소를 가져오거나 검색하는 경우 HashSet을 사용하는 것이 가장 좋은 방법 중 하나이다.
add()메서드를 사용하여 데이터를 삽입한다.
HashMap보다 느리다.
- 형태
삽입되는 객체 자체를 저장하기 때문에 중복값이 허용되지 않는다.
AbstractSet을 확장하고 Set
HashSet.contains() : 항목이 HashSet의 인스턴스에 있는지 여부를 확인하는 메서드이다.
HashSet.addAll() : 주어진 컬렉션에 저장된 모든 객체를 추가한다.
HashSet.isEmpty() : HashSet이 비어잇는지 확인한다.
HashSet.toArray() : 저장된 객체들을 객체배열의 형태로 반환한다.
해시 문제 폰켓몬
import java.util.*;
class Solution {
public int solution(int[] nums) {
int answer = 0;
int lng=nums.length/2;
HashSet<Integer> hash=new HashSet<Integer>();
for(int i=0; i<nums.length; i++){
hash.add(nums[i]);
if(lng<hash.size()){
answer=lng;
}else{
answer=hash.size();
}
}
return answer;
}
}