Hash 자료구조, hashCode()와 equals() 재정의, List/Map/Set, String/StringBuilder/StringBuffer, int/Integer

Hash 자료구조는 key-value 형태로 저장되는 자료구조이고 해시 함수를 이용해서 저장, 검색하기 때문에 해시충돌이 일어나지 않는 경우에 속도가 빠르다는 장점이 있고 메모리를 미리 만들어놓고 메모리를 사용하지 않는 경우가 있기 때문에 공간 효율이 안좋고 해시 함수에 의해 해시 충돌이 많이 일어나는 경우 성능이 안좋아 질 수 있다는 단점이 있습니다.

 

 

해시 충돌이란 해시 자료구조에 저장을 할 때 키로 해시함수를 이용해 계산한 해시를 주소로 하는 위치에 값을 저장하는건데, 이 때 서로 다른 키를 해시 함수로 계산했는데 같은 값이 나오는 경우를 말합니다.

그래서 해시 충돌이 일어나느 경우 개방형주소 방벙, 채이닝 방법 같은 걸 사용해서 해결을 합니다.

 

개방형 주소는 해시충돌이 일어나는 경우 다른 해시값을 주소로하는 위치에 데이터를 저장하는 방법입니다. 

미리 만들어둔 공간을 다 사용하기 때문에 메모리 효율이 좋다는 장점이 있지만 밀도가 높아질 경우 성능이 급격히 안 좋아진 다는 특징이 있습니다.

 

채이닝 방법은 해시충돌이 일어난 경우에 충돌이 일어난 공간에서 리스트나 트리형태로 추가적인 공간에서 저장을 하는 방법입니다. 미리 선언해둔 공간 외에 외부의 공간을 사용하고 구현이 간단하다는 특징이 있습니다.

 

java에서 HashMap에서는 개방형주소 방법은 밀도가 높아질 경우 성능이 성능이 급격히 안좋아진다는 단점이 있기 때문에 체이닝 기법을 사용합니다.

 

 

 

[java] hashcode()와 equals() 메서드는 언제 사용하고 왜 사용할까? (tistory.com)

[Java] equals() & hashcode() 메서드는 언제 재정의해야 할까? (velog.io)

== : 객체의 주소값 비교

String.equals() : 값을 비교해서 boolean형으로 반환

Object.hashcode() : 객체 교유의 해시코드를 int형으로 반환

 

객체를 HashMap, HashSet에 저장할 때 equals와 hascode를 재정의 하는 이유

- hash 자료구조에 저장할 때 해시충돌이 일어나는 경우 충돌이 일어난 해시코드의 공간에 linkedList 또는 TreeMap 형태로 저장이 되기 때문에 같은 HashCode여도 값은 다를 수 있기 때문에 같은 객체를 hashSet 자료 구조에 넣었을 때 중복을 피하려면 hascode와 equals 모두 재정의 해야 합니다.

 

 

 

 

 

Java - Collection과 Map의 종류(List, Set, Map) (tistory.com)

List 는 순서를 보장하는 자료구조입니다.

 

ArrayList는 배열 형태로 저장됩니다.

따라서 특정 위치 검색시 index로 검색을 해서 속도가 빠릅니다.

그리고 특정 위치 삽입/삭제는 index를 미뤄내는 작업이 필요해서 속도가 느립니다.

또한 삽입 시에는 기존 배열 크기의 2배 크기로 새롭게 메모리에 할당해서 기존 배열을 복사하면서 새로운 값을 집어넣기 때문에 메모리를 많이 잡아 먹게 된다.

 

LinkedList는 Node가 앞뒤로 연결되어있는 구조로 저장됩니다

따라서 특정 위치 검색시 특정 위치까지 타고 타고 가야  하기 때문에 속도가 느립니다.

그리고 특정 위치 삽입/삭제 시에는 그 위치까지 타고타고 가는게 필요하지만 노드 연결 부분만 새로 해주면 되기 떄문에 

ArrayList에 비해 성능이 좋고 메모리 측면에서도 유리합니다.

 

Vector는 ArrayList처럼 배열로 만들어진 List인데 만들어진 것인데 메서드에 synchronized 키워드를 사용하기 때문에 Thread-Safe합니다.

 

Set은 중복이 허용되지 않고 순서가 없는 자료구조입니다.

HashSet은 Hash 자료구조로 저장되는 set입니다.

LinkedHashSet은 중복이 허용되지 않지만 순서는 있는 자료구조입니다.

TreeSet은 중복이 없고 순서도 없지만 데이터를 정렬하여 저장하는 자료구조입니다.

 

Map은 key,value 형태로 저장이 되고 key는 중복을 허용하지 않는 자료구조입니다.순서가 없습니다.

HashMap은 hash자료구조 형태로 저장되는 map입니다.

LinkedHashMap은 순서가 보장되는 Map입니다.

TreeMap은 데이터가 정렬되어 저장되는 Map입니다.

HashTable은 HashMap과 비슷한데 synchronized 키워드를 메서드에 사용해서 Thead-Safe하다는 특징이 있습니다.

 

 

[JAVA] ☕ String / StringBuffer / StringBuilder 차이점 & 성능 비교 (tistory.com)

String은 final Char[]에 저장이 되기 때문에 불변형으로 String 연산을 하면 새로운 메모리에 할당이 됩니다. 그래서 스트링 연산이 많은 경우에는 성능이 안 좋아질 수 있습니다.

StringBuilder, StringBuffer는 가변형이라 스트링 연산이 있어도 같은 메모리에서 값만 변합니다. 그래서 스트링 연산을 하는 경우에 적합하고 StringBuffer 내부에서는 Synchronized 키워드를 사용하기 때문에 Thread-Safe합니다.

 

 

 

int/Integer

int와 Integer 차이 (Primitive 자료형과 Wrapper 클래스 관계) (tistory.com)

Integer는 기본자료형(primitive type)인 int에 대응 되는 wrapper 클래스입니다.

Integer 특징으로는

• null값을 지원하기 때문에 값이 없는 걸 표현할 수 있습니다. (int형은 자동으로 0으로 초기화 됩니다.)
• 제네릭(Generic) 타입에는 클래스만 지정가능하기 때문에 제네릭에 정수형 타입으로 지정하고 싶을 때 사용합니다.
• 컬렉션(collection)에는  기본타입이 아닌 래퍼클래스만 저장 가능합니다.
• Object로 변환해서 사용하고 싶을 때 래퍼클래스인 경우 변환이 가능합니다.