TIL 정리_48(Hash Table, ArrayList)

https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA

유튜브 - 엔지니어 대한민국의 자료구조 강의를 듣고 정리한 내용입니다 

 

 

 

해시테이블(hash table)

검색하고자하는 key값을 입력받아 해시 함수로 반환받은 해시 코드를 배열의 인덱스로 환산하여 데이터에 접근하는 방식의 자료구조이다

key -> HashCode -> Index -> Value

해시함수 : 특정한 규칙을 읽어 입력받은 key값을 값에 관계없이 동일한 코드를 반환한다

 

 

Hash Table

검색속도가 매우 빠르다 -> 배열 공간을 고정된 크기만큼 마련해놓고 해시코드를 배열의 index로 사용하기 때문이다

배열의 방을 나눌 때 규칙을 잘 만드는게 중요하다 -> Hash Algorithm을 의미

 

collision : 알고리즘이 좋지 않을 때 동일한 코드가 발생하여 충돌현상이 일어나는 것을 말한다 

collision이 많은 경우 시간복잡도가 늘어난다

해시함수는 때론 서로 다른 키, 값으로 동일한 값을 내보내기도 한다

-different keys -> same code

-different code -> same index

->하나의 배열 방에 겹쳐서 저장되는 것 : collision

 

ConvertToIndex(Hash code) -> 해시코드를 index로 반환한다

hashcode % size = 저장되는 위치

 

 

해시테이블 예제코드

 

import java.util.LinkedList; class HashTable { class Node { //저장할 데이터를 담는다 String key; String value; public Node(String key, String value) { //키와 값을 받아 할당한다 this.key = key; this.value = value; } String value() { return value; } void value(String value) { this.value = value; } } LinkedList<Node>[] data; //데이터를 저장할 LinkedList HashTable(int size) { //해시테이블의 크기를 미리 정해야한다 this.data = new Linkedlist[size]; } int getHashCode(String key) { //key를 입력받아 반환 int hashcode = 0; for(char c : key.toCharArray()) { hashcode += c; } return hashcode; } int convertToIndex(int hashcode) { //hashcode를 index로 변환 return hashcode % data.length; } Node searchKey(LinkedList<Node> list, String key) { //노드의 키가 검색하려는 것과 같은지 확인 if (list == null) return null; for(Node node : list) { if(node.key.equals(key)) { return node; } } return null; } void put(String key, String value) { //key와 hashcode를 받아온다 int hashcode = getHashCode(key); int index = convertToIndex(hashcode); System.out.println(key + “, hashcode(” + hashcode + “), index(” + index + “)”); //데이터를 넣을 때 해시코드가 무엇인지 배열 방은 어디로 배정 받았는지 확인 LinkedList<Node> list = data[index]; if ( list == null) { list = new LinkedList<Node>(); data[index] = list; } Node node == searchKey(list, key); if (node == null) { //데이터가 없다 list.addLast(new Node(key, value)); //받아온 정보로 노드객체를 생성해 리스트에 추가 } else { node.value(value); } } String get(String key) { //key를 가지고 데이터를 가져오는 get 함수 정의 int hashcode = getHashCode(key); int index = convertToIndes(hashcode); LinkedList<Node> list = data[index]; Node node = searchKey(list, key); return node == null? “Not found” : node.value(); //노드를 못 찾으면 Not found 찾으면 노드의 값을 반환한다 } } public class Test { public static void main(String args[]) { HashTable h = new HashTable(3); h.put(“sung”, “She is pretty”); h.put(“jin”, “She is a model”); h.put(“hee”, “She is an angel”); h.put(“min”, “She is cute”); System.out.println(h.get(“sung”)); System.out.println(h.get(“jin”)); System.out.println(h.get(“hee”)); System.out.println(h.get(“min”)); } }

 

 

 

 

ArrayList

데이터를 추가하는대로 사이즈가 늘어난다

-> ArrayList의 검색시간은 O(1)

->배열 방이 다 차면 배열의 크기를 2배로 늘려주는 작업을 한다

-> 검색할때는 고정된 배열에서 검색한다

 

 

Doubling

2배 큰 크기의 새로운 배열을 선언하고 기존 배열에 있는 작업을 새로운 배열에 그대로 복사하는 것을 Doubling이라고 한다 //입력시간 : O(1)

평균적으로 ArrayList의 검색시간과 입력시간이 O(1)이다

 

 

ArrayList 예제코드 

 

class ArrayList { private Object[] data; //데이터 배열 선언 private int size; //크기  private int index; //위치  public ArrayList() { this.size = 1; this.data = new Object[this.size]; this.index = 0; } public void add(Object obj) { //배열방이 다 찼는지 확인 if(this.index == this.size –1) { doubling(); } data[this.index] = obj; //공간이 있다면 데이터 추가 this.index++; } private void doubling() { //doubling 함수 정의 this.size = this.size * 2; //2배 큰 사이즈로 정의 Object[] newData = new Object[this.size]; for(int I = 0; I < data.length; I++) { newData[i] = data[i]; } this.data = newData; //배열방의 주소가 현재 주소 } public Object get(int I) throws Exception { if(i > this.index-1) { //인덱스가 데이터 범위 내에있는지 확인 후 예외 throw throw new Exception(“ArrayIndexOutOfBouond”); } else if (i < 0) { throw new Exception(“Negative Value”); } return this.data[i]; } public void remove(int I) throws Exception { if(i > this.index-1) { throw new Exception(“ArrayIndexOutOfBouond”); } else if ( i< 0) { throw new Exception(“Negative Value”);; } for(int x = i; x < this.data.length –1; x++) { data[x] = data[x + 1]; } this.index--; } } public class Test { public static void main(String[] args) throws Exception { ArrayList al = new ArrayList(); al.add(“0”); al.add(“1”); al.add(“2”); al.add(“3”); al.add(“4”); al.add(“5”); al.add(“6”); al.add(“7”); al.add(“8”); al.add(“9”); System.out.println(al.get(5)); //5번방에 있는 데이터 가져오기 al.remove(5); //데이터 지우기 System.out.println(al.get(5)); } }