[자료구조] Hash/HashMap/정렬

프로그래머스 문제를 풀어보다가, 자료구조 Hash 에 대해서 부족한 부분이 많았다는걸 깨닫고

포스팅을 남깁니다. 대부분 블로그를 긁어온 것이니, 자세한 사항은 해당 블로그에 들어가서 확인해주세요.

1. Hash

Hash란 Key-value 값으로 매칭되는 자료구조로써,

key값은 특정 연산(해쉬알고리즘)을 사용하여 값을 주고,

value는 원하는 값을 넣으면 됩니다.

Key 값은 중복이 안되지만,

Value는 중복이 됩니다.

( 그 이유는 Hash chaining 기술을 이용해서 인데, 자세한 부분은 생략 )

이렇게 했을 때, 장점은?

Hashing을 사용하기 때문에 많은 양의 데이터 검색에 뛰어난 성능을 보인다.

https://blog.naver.com/kiho0530/150138013167

---

2. Hash 생성자 / 메서드 설명

 

생성자 / 메서드	설명
HashMap()	- HashMap 객체를 생성 ex) HashMap<String , Integer> map = new HashMap<String , Integer>();       Map<String, Integer> map = new HashMap<String, integer>();
HashMap(int initlalCapacity)	- 지정된 값을 초기 용량으로 하는 HashMap객체를 생성한다.
HashMap(int initlalCapacity, float loadFactory)	- 지정된 값을 초기용량과 load factory의 HashMap 객체를 생성한다.
HashMap(Map m)	- 주어진 Map에 저장된 모든 요소를 포함하는 HashMap을 생성한다.
void clear()	- HashMap에 저장된 모든 객체를 제거한다.  ex) map.clear();
Object clone()	- 현재 HashMap을 복제하여 반환한다.  ex) newmap = (HashMap)map.clone();
boolean containsKey(Object Key)	- HashMap에 지정된 키(Key)가 포함되어 있는지 알려준다.
boolean containsValue(Object Value)	- HashMap에 지정된 값(Value)가 포함되어 있는지 알려준다.
Set entrySet()	- HashMap에 저장된 Key - Value갑슬 엔트리(키와 값을 결합)의 형태로 Set에 저장하여 반환 ex) map.put("A", 1);       map.put("B", 2);       map.put("C", 3);       Set set = map.entrySet();       System.out.println("set values are" + set);       (result) set values : [A=1,B=2,C=3]
Object get(Object Key)	- 지정된 Key 의 값을 반환한다.  ex) map.put("A", 1);       map.put("B", 2);       map.put("C", 3);       String val = (String)map.get("B"); System.out.println("Value for key B is: " + val);   (result) Value for key B is 2
bloolean isEmpty	- HashMap이 비어있는지 확인한다. ex) boolean val = map.isEmpty();
Set keySet()	- HashMap에 저장된 모든 키가 저장된 Set을 반환한다. ex) map.put("A", 1);       map.put("B", 2);       map.put("C", 3);       Set keyset = map.keySet();       System.out.println("Key set values are" + keyset);       (result) Key set values are [A,B,C]
Object put(Object Key, Object Value)	- HashMap에 키와 값을 저장. ex) map.put("A", "aaa");       map.put("B", "bbb");       map.put("C", "ccc");
void putAll(Map m)	- Map에 해당하는 모든 요소를 HashMap에 저장한다.
Object remove(Object Key)	- HashMap에서 지정된 키로 지정된 값을 제거한다. ex) map.remove("key");
int size()	- HashMap에 저장된 요소의 개수를 반환한다.
Collection values()	- HashMap에 저장된 모든 값을 컬렉션 형태로 반환한다.

 

출처: https://vaert.tistory.com/107 

---

import java.util.Iterator;

import java.util.Map;

import java.util.Set;

import java.util.HashMap;

 

pubilc class HashMapDemo

{

public static void main(String[] args) 

{

HashMap<String, Integer> fruitMap = new HashMap();

fruitMap.put("사과", 1000);

fruitMap.put("배", 2000);

fruitMap.put("자두", 3000);

fruitMap.put("수박", 4000);

 

// get() --> Key에 해당하는 Value를 출력한다.

System.out.println( fruitMap.get("자두") );   // 3000

 

        // values() --> 저장된 모든 값 출력

System.out.println( fruitMap.values() ); // [1000, 2000, 3000, 4000]

 

// HashMap에 넣은 Key와 Value를 Set에 넣고 iterator에 값으로 Set정보를 담에 준다.

// Interator itr = fruitMap.entrySet().interator(); 와 같다.

Set<Entry<String, Integer>> set = fruitMap.entrySet();

Interator<Entry<String, Integer>> itr = set.interator();

while (itr.hasNext())

{

Map.Entry<String, Integer> e = (Map.Entry<String, Integer>)itr.next();

System.out.println("이름 : " + e.getKey() + ", 가격 : " + e.getValue() + "원");

}

}

---

3. map을 이용해서 key나 value 값을 정렬

Key에 의한 정렬 

TreeMap을 사용한다. 

- TreeMap 은 중복을 허용하지 않고 Key 값을 기준으로 정렬을 해주는 자료구조 입니다.

(HashMap 은 내부 hash 값에 따라 키순서가 정해지므로 특정 규칙없이 출력됩니다.)

역 정렬 또한 가능합니다.

Sample code

//메인메소드에서 구현

Map<Double,Integer> hashMap = new HashMap<Double,Integer>();

hashMap.put(1.1,99);

hashMap.put(2.2,70);

hashMap.put(13.3,89);

hashMap.put(7.7,79);

hashMap.put(10.1,99);

TreeMap<Double,Integer> tm = new TreeMap<Double,Integer>(hashMap);

 

Iterator<Double> iteratorKey = tm.keySet( ).iterator( );   //키값 오름차순 정렬(기본)

while(iteratorKey.hasNext()) {

  Double key = iteratorKey.next();

  System.out.println(key+","+tm.get(key));

 }

결과 출력

Value에 의한 정렬 

comparator을 직접 구현하여 정렬 할 수 있습니다.

아래 코드는 key 목록을 리스트에 담고, 해당 리스트를 value를 기준으로 정렬하는 방식으로 구현 되었습니다.

Sample code

  //메인메소드에서 구현

        Map<String,Integer> map = new HashMap<String,Integer>();

        map.put("a",3);

        map.put("b",12);

        map.put("c",54);

        map.put("d",51);

        map.put("e",8);

         

        System.out.println("------------sort 전 -------------");

        Iterator iterator = map.keySet().iterator();

        while(iterator.hasNext {

            String temp = (String) iterator.next();

            System.out.println(temp + " = " + map.get(temp));

        }

         

        Iterator it = sortByValue(map).iterator();

         

        System.out.println("------------sort 후 -------------");

        while(it.hasNext()) {

            String temp = (String) it.next();

            System.out.println(temp + " = " + map.get(temp));

        }

//별도의 스태틱 함수로 구현

public static List sortByValue(final Map map) {

        List<String> list = new ArrayList();

        list.addAll(map.keySet());

         

        Collections.sort(list,new Comparator() {

             

            public int compare(Object o1,Object o2) {

                Object v1 = map.get(o1);

                Object v2 = map.get(o2);

                 

                return ((Comparable) v2).compareTo(v1);

            }

             

        });

        Collections.reverse(list); // 주석시 오름차순

        return list;

    }

출처: https://ithub.tistory.com/34

---

https://programmers.co.kr/learn/courses/30/lessons/42577

전화번호부 문제