Java : ArrayList, LinkedList, HashMap

본인이 주력으로 사용하는 언어에서 자료구조와 관련 된 클래스가 내부적으로 어떻게 동작하는지 한 가지 사례를 정하여 작성해주세요. ex) ArrayList, HashMap 등등
출처 : 원티드 프리온보딩 챌린지 백엔드 사전과제

• ArrayList
  ArrayList 객체를 생성하면 내부에서는 elementData 라는 Object 타입의 Array가 생성됩니다. 이 때문에 ArrayList는 Array처럼 임의의 인덱스에 무작위로 접근할 수 있게 됩니다. add 메소드로 배열의 크기를 늘릴 때 내부에서는 새롭게 계산된 크기의 배열을 생성해 배열의 내용을 복사하고 기존 배열을 삭제합니다.

• LinkedList
  LinkedList 객체를 생성하면 내부에는 Node 클래스 객체가 생성됩니다. Node에는 데이터와 함께 이전 노드와 다음 노드의 주소가 함께 저장됩니다. 데이터 추가나 삭제 시 노드에 저장된 이전/다음 노드의 주소만 변경됩니다.

• HashMap
  HashMap의 내부구조는 배열로 되어 있습니다. Key는 해시 함수를 통해 내부 배열의 인덱스가 됩니다. 해시 함수 산출 시 동일한 해시 코드가 산출될 수 있고 이를 해시 충돌이라 하며, 이를 방지하기 위한 방법으로 Java의 HashMap의 경우 충돌을 대비해 배열의 점유율에 따라 크기를 조절하고 있고, Separate Chaining 방식을 사용하고 있습니다. Separate Chaining 은 동일한 해시 코드가 있을 경우 LinkedList로 관리하고, 8개 이상인 경우 Tree로 변경하여 관리하는 방식입니다.