Week 4 of Data structures - Direct addressing and chaining
이번주차의 강의에서는 Hash table에 대한 내용을 학습한다. 첫번째로 Direct addressing and chaining에 관한 내용이다.
Hashing이라는 기술의 적용 분야에 대해 간략히 언급하고 넘어간다. 우선 프로그래밍 언어 중 Java의 HashMap, Python이 dict가 Hash table의 역할을 한다고 한다.
또한 컴퓨터에서는 Hash table을 통해 긴 path와 디스크명을 mapping하여 간략화 시켜 사용한다고 한다.
Hash table은 보안에서도 사용되고 Hash function을 통해 변환이 多:1로 되기 때문에 제대로 역변환이 어려워 안정성이 확보된다.
이번에는 IP address를 통해 특정 서비스로 접근할 때 Hash table을 사용하게 된 이유를 간략히 보여준다. 우선 IP address는 위와 같은 형식이다. IPv4라는 명칭을 가지며 000.000.000.000와 같은 자리수를 가진다. 이때 각 자리별 숫자는 0~255이다. 이 숫자들로 표현할 수 있는 최대 수는 2^32이며 몇년전 최대 수를 곧 초과할 것이라는 예측으로 그보다 더 표현이 가능한 IPv6를 도입하는데 이번에는 IPv4에 대해서만 언급한다고 한다.
어떠한 웹 서비스에 어떤 IP를 사용하는 이용자가 언제 접근을 했었는지에 대한 Log를 위와 같이 테이블 형태로 정리한다면 꽤나 잘 파악할 수 있다. 하지만 수많은 IP가 접근한다면 이를 모두 위와 같은 형태로 저장한다면 이에 대한 용량문제를 생각하게 될 것이다.
또한 같은 IP가 최근 몇시간동안 몇번이나 접근했는지 등에 대한 정보를 알고 싶을 때 IP Access List가 사용되는 것을 상기시키면서,
Log를 처리할 때 위와 같은 특징들이 있다고 한다.
모든 쿼리에 대해 처리하는 것은 위에 언급되어 있는 것처럼 너무 많은 시간을 소요하니 1시간만 추리자면 최신의 데이터일수록 하단에 위치하며 각 IP에 대해 counter를 증가시키면 효과적으로 처리가 가능하다.
위의 쿼리를 처리하는 Main loop에 대한 pseudo code이다.
중간에 삽입된 UpdataAccessList, AccessedLastHour API에 대한 코드이다.
이제 다시금 초반에 언급했던 Log에서 IP주소를 개별적으로 모두 저장했을 때 용량이 너무 커지는 현상을 방지하기 위한 방안으로 넘어가 보도록 하겠다.
우선 IP주소가 어떻게 변환이 되는지 원리부터 간략히 살펴보자면 0.0.0.0과 같은 형태이며 각 숫자는 0~255까지의 정수 범위를 가진다. 또한 각 자리를 2진수로 변환하여 이를 자릿수에 맞게 다시 10진수로 변환하면 이것이 IP주소의 정수값이 된다.
바로 퀴즈가 나오는데 69.171.230.68의 주소값을 변환하면 0100 0101 1010 1011 1110 0110 0100 0100이다. 이들을 모두 이어붙여서 10진수로 다시 변환하면 1168893508가 되는 것을 알 수 있었다.
위에서 진행한 int(IP)의 수식은 위와 같다. 이들은 다시금 UpdateAccessList에 활용이 된다.
AccessedLastHour(IP)에도 적용이 된다.
위의 연산들의 복잡도가 O(1)임을 알려주며 IPv6는 적합하지 않다고 설명한다.
하지만 보다시피 10진수로도 굉장히 큰 수가 되어 저장하는데 메모리 부담이 크다. 이를 해결하는 방법에 대해 알아보자.
이번에 좀 다른 UpdateAccessList를 보게되는데 이번에는 Log에 기록된 IP를 i로 대체하여 굉장히 작은수로 저장하는 List에 Append하는 형식으로 바뀐것을 알 수 있다. decounter역할로는 Pop 기능을 통해 진행하는 것을 볼 수 있다.
AccessedLastHour와 AccessCountLastHour의 경우도 굉장히 간략화 된것을 알 수 있고 주요 쟁점은 IP주소가 존재하는 지 여부에 따라 동작하는 것이다.
정리하면 n개의 Active IP들로 맵핑이되며 메모리 사용은 O(n)를 따르게 된다. 이외의 동작들의 복잡도는 위와 같다.
이제 Hash Function을 이용해 IP를 엔코딩하여 숫자를 작게하여 active IP로 변환하는 것에 대해 보게된다.
Hash Function의 정의는 위와 같으며 언급했던 것처럼 어떠한 정수를 또다른 리스트에 대입하는 것을 말한다.
Hash function의 특징은 위와 같으며 아무래도 작은수로 대체하므로 빠를 수 밖에 없다.
하지만 Hash function의 단점으로 충돌이 발생할 수도 있는데 이는 맵핑하는 과정에서 이전 값들이 달라도 맵핑된 값들이 같을 수 있기 때문이다.
위에서 말해왔듯 Map이라는 개념은 대칭시키는 것이며 여기서는 데이터 구조로써 HasKey, Get, Set이라는 메쏘드를 활용한다.
이제 Mapping을 하는 방식을 Chaining이라고 하며 어떤방식으로 진행되는지 보려한다.
173.194.71.102라는 IP주소를 hash function을 통하여 4로 대체하고 이에 대한 카운터도 추가한다. 이때 S 리스트에 4번째 index에 해당 주소를 연결하며 마치 체인연결하듯 진행이 된다.
다음엔 69.171.230.68은 1로 대응하고,
마찬가지로 1번째 index에 연결을 해준다.
같은 주소가 다시 출현하면 위와 같이 카운터만 상승하게 되고,
다른 주소이지만 같은 index에 대응이 된다면,
위와 같은 모습으로 Chaining을 진행하게 된다.
위의 동작들을 HasKey라는 기능으로 표현이 가능하다. h는 hash function이며 S는 새로이 부여될 값들, O는 S안의 인덱스, v는 기존 값을 말하며 A는 chaining된 리스트이다.
Get은 같은 인덱스의 다른 value를 반환해주는 기능을 가진다.
Set은 Object의 index가 존재여부에 따라 chaining이나 append를 수행하는 기능이다.
이제 c를 가장 긴 chain이라고 할 때 HasKey, Get, Set의 시간 복잡도는 위와 같다.
또한 n개의 key(index)와 mapping된 m개의 hash function이 있다면 이들의 메모리 소요시간 복잡도는 위와 같게 된다.
이제 마지막으로 Hash table에 대해 살펴본다. 우선 Set은 데이터 구조로써 Add, Remove, Find라는 메쏘드들로 구성이 된다.
V값은 true, false로 반환이 되며 S내에 존재하면 true가 될 것이다. 또한 Chaining 시 (O, v)의 짝으로 저장하는 대신 O의 값만 저장하게 된다고 한다.
Find를 통해서는 해당 배열에 값이 존재하는지 유무를 알 수 있고,
Add는 리스트에 값이 존재하지 않을 때 추가하는 기능이며,
Remove는 해당 지정값을 삭제하는 기능이다.
Hash Table에 대한 정의 이며 hashing을 활용한 set이나 map을 hash table이라고 부른다.
프로그래밍 언어에서 Set과 Map에 대응되는 데이터구조를 비교한 장표이다.
결론이며 아쉽게도 이번 강의는 전달하고자 무엇인지 잘 캐치하기 힘들었다. 좀 더 자료를 찾고 이해하는 시간을 가져야겠다.
이번주차의 강의에서는 Hash table에 대한 내용을 학습한다. 첫번째로 Direct addressing and chaining에 관한 내용이다.
Hashing이라는 기술의 적용 분야에 대해 간략히 언급하고 넘어간다. 우선 프로그래밍 언어 중 Java의 HashMap, Python이 dict가 Hash table의 역할을 한다고 한다.
또한 컴퓨터에서는 Hash table을 통해 긴 path와 디스크명을 mapping하여 간략화 시켜 사용한다고 한다.
Hash table은 보안에서도 사용되고 Hash function을 통해 변환이 多:1로 되기 때문에 제대로 역변환이 어려워 안정성이 확보된다.
이번에는 IP address를 통해 특정 서비스로 접근할 때 Hash table을 사용하게 된 이유를 간략히 보여준다. 우선 IP address는 위와 같은 형식이다. IPv4라는 명칭을 가지며 000.000.000.000와 같은 자리수를 가진다. 이때 각 자리별 숫자는 0~255이다. 이 숫자들로 표현할 수 있는 최대 수는 2^32이며 몇년전 최대 수를 곧 초과할 것이라는 예측으로 그보다 더 표현이 가능한 IPv6를 도입하는데 이번에는 IPv4에 대해서만 언급한다고 한다.
어떠한 웹 서비스에 어떤 IP를 사용하는 이용자가 언제 접근을 했었는지에 대한 Log를 위와 같이 테이블 형태로 정리한다면 꽤나 잘 파악할 수 있다. 하지만 수많은 IP가 접근한다면 이를 모두 위와 같은 형태로 저장한다면 이에 대한 용량문제를 생각하게 될 것이다.
또한 같은 IP가 최근 몇시간동안 몇번이나 접근했는지 등에 대한 정보를 알고 싶을 때 IP Access List가 사용되는 것을 상기시키면서,
Log를 처리할 때 위와 같은 특징들이 있다고 한다.
모든 쿼리에 대해 처리하는 것은 위에 언급되어 있는 것처럼 너무 많은 시간을 소요하니 1시간만 추리자면 최신의 데이터일수록 하단에 위치하며 각 IP에 대해 counter를 증가시키면 효과적으로 처리가 가능하다.
중간에 삽입된 UpdataAccessList, AccessedLastHour API에 대한 코드이다.
이제 다시금 초반에 언급했던 Log에서 IP주소를 개별적으로 모두 저장했을 때 용량이 너무 커지는 현상을 방지하기 위한 방안으로 넘어가 보도록 하겠다.
우선 IP주소가 어떻게 변환이 되는지 원리부터 간략히 살펴보자면 0.0.0.0과 같은 형태이며 각 숫자는 0~255까지의 정수 범위를 가진다. 또한 각 자리를 2진수로 변환하여 이를 자릿수에 맞게 다시 10진수로 변환하면 이것이 IP주소의 정수값이 된다.
바로 퀴즈가 나오는데 69.171.230.68의 주소값을 변환하면 0100 0101 1010 1011 1110 0110 0100 0100이다. 이들을 모두 이어붙여서 10진수로 다시 변환하면 1168893508가 되는 것을 알 수 있었다.
위에서 진행한 int(IP)의 수식은 위와 같다. 이들은 다시금 UpdateAccessList에 활용이 된다.
AccessedLastHour(IP)에도 적용이 된다.
위의 연산들의 복잡도가 O(1)임을 알려주며 IPv6는 적합하지 않다고 설명한다.
하지만 보다시피 10진수로도 굉장히 큰 수가 되어 저장하는데 메모리 부담이 크다. 이를 해결하는 방법에 대해 알아보자.
이번에 좀 다른 UpdateAccessList를 보게되는데 이번에는 Log에 기록된 IP를 i로 대체하여 굉장히 작은수로 저장하는 List에 Append하는 형식으로 바뀐것을 알 수 있다. decounter역할로는 Pop 기능을 통해 진행하는 것을 볼 수 있다.
AccessedLastHour와 AccessCountLastHour의 경우도 굉장히 간략화 된것을 알 수 있고 주요 쟁점은 IP주소가 존재하는 지 여부에 따라 동작하는 것이다.
이제 Hash Function을 이용해 IP를 엔코딩하여 숫자를 작게하여 active IP로 변환하는 것에 대해 보게된다.
Hash Function의 정의는 위와 같으며 언급했던 것처럼 어떠한 정수를 또다른 리스트에 대입하는 것을 말한다.
Hash function의 특징은 위와 같으며 아무래도 작은수로 대체하므로 빠를 수 밖에 없다.
하지만 Hash function의 단점으로 충돌이 발생할 수도 있는데 이는 맵핑하는 과정에서 이전 값들이 달라도 맵핑된 값들이 같을 수 있기 때문이다.
위에서 말해왔듯 Map이라는 개념은 대칭시키는 것이며 여기서는 데이터 구조로써 HasKey, Get, Set이라는 메쏘드를 활용한다.
이제 Mapping을 하는 방식을 Chaining이라고 하며 어떤방식으로 진행되는지 보려한다.
173.194.71.102라는 IP주소를 hash function을 통하여 4로 대체하고 이에 대한 카운터도 추가한다. 이때 S 리스트에 4번째 index에 해당 주소를 연결하며 마치 체인연결하듯 진행이 된다.
다음엔 69.171.230.68은 1로 대응하고,
마찬가지로 1번째 index에 연결을 해준다.
같은 주소가 다시 출현하면 위와 같이 카운터만 상승하게 되고,
다른 주소이지만 같은 index에 대응이 된다면,
위와 같은 모습으로 Chaining을 진행하게 된다.
위의 동작들을 HasKey라는 기능으로 표현이 가능하다. h는 hash function이며 S는 새로이 부여될 값들, O는 S안의 인덱스, v는 기존 값을 말하며 A는 chaining된 리스트이다.
Get은 같은 인덱스의 다른 value를 반환해주는 기능을 가진다.
Set은 Object의 index가 존재여부에 따라 chaining이나 append를 수행하는 기능이다.
이제 c를 가장 긴 chain이라고 할 때 HasKey, Get, Set의 시간 복잡도는 위와 같다.
또한 n개의 key(index)와 mapping된 m개의 hash function이 있다면 이들의 메모리 소요시간 복잡도는 위와 같게 된다.
이제 마지막으로 Hash table에 대해 살펴본다. 우선 Set은 데이터 구조로써 Add, Remove, Find라는 메쏘드들로 구성이 된다.
V값은 true, false로 반환이 되며 S내에 존재하면 true가 될 것이다. 또한 Chaining 시 (O, v)의 짝으로 저장하는 대신 O의 값만 저장하게 된다고 한다.
Find를 통해서는 해당 배열에 값이 존재하는지 유무를 알 수 있고,
Add는 리스트에 값이 존재하지 않을 때 추가하는 기능이며,
Remove는 해당 지정값을 삭제하는 기능이다.
Hash Table에 대한 정의 이며 hashing을 활용한 set이나 map을 hash table이라고 부른다.
프로그래밍 언어에서 Set과 Map에 대응되는 데이터구조를 비교한 장표이다.
결론이며 아쉽게도 이번 강의는 전달하고자 무엇인지 잘 캐치하기 힘들었다. 좀 더 자료를 찾고 이해하는 시간을 가져야겠다.
저 변함없이 앞에 손모으고 있는게 복붙한거같아
답글삭제