수업 1정적 환경을 위한 충돌 전략 선택: 오픈 어드레싱 vs 배열을 사용한 정적 별도 체이닝고정 메모리 시스템을 위한 오픈 어드레싱과 정적 별도 체이닝을 비교하며, 캐시 동작, 단편화, 구현 복잡성, 임베디드 C 프로젝트에서 충돌 전략 선택 지침을 분석합니다.
오픈 어드레싱 속성 검토정적 별도 체이닝 검토메모리 레이아웃과 캐시 친화성복잡성과 구현 노력전략 선택 지침수업 2메모리와 시간 복잡도: 최악 및 예상 프로브 문서화, 임베디드용 테이블 로드 팩터 권장사항정적 해시 테이블의 메모리와 시간 복잡도를 분석하며, 최악 케이스 및 예상 프로브 수, 로드 팩터 제한, 임베디드 센서 애플리케이션에 맞춘 실용적 크기 권장사항을 문서화합니다.
최악 케이스 프로브 길이 분석랜덤 해싱 하의 예상 프로브로드 팩터가 성능에 미치는 영향메모리 사용량과 테이블 크기임베디드 특화 튜닝 지침수업 3안전한 포인터 처리: 포인터 대신 인덱스 사용, 경계 검사, NULL 역참조 방지정적 해시 테이블에서 원시 포인터 대신 인덱스를 사용하여 안전한 포인터 처리를 다룹니다. 경계 검사 강제, C 코드에서 NULL 역참조와 매달린 참조를 방지하는 API 설계를 배웁니다.
정적 테이블에서 인덱스 vs 포인터견고한 경계 검사 구현NULL과 매달린 참조 방지인덱스를 포인터로 안전 변환안전성을 강제하는 API 패턴수업 4오픈 어드레싱 기술: 선형 프로빙, 이차 프로빙, 토브스톤, 동적 메모리 없이 삭제 의미론정적 테이블에서 오픈 어드레싱을 상세히 설명하며, 선형 및 이차 프로빙, 토브스톤 마커, 동적 할당 없이 프로브 체인을 보존하고 예측 가능한 성능을 유지하는 삭제 규칙을 다룹니다.
선형 프로빙: 알고리즘과 트레이드오프이차 프로빙: 클러스터링 동작토브스톤 마커 설계와 사용삭제 의미론과 프로브 체인 복구가득 찬 테이블 감지와 실패 모드수업 5원형 버퍼와 통합: 최신 읽기 유지와 일관성 정책(쓰기 순서, 타임스탬프)정적 해시 테이블이 원형 버퍼와 협력하여 최신 센서 읽기를 유지하는 방법을 탐구합니다. 쓰기 순서 정의, 신선도를 위한 타임스탬프 사용, 업데이트나 동시 접근 시 일관성 유지 방법을 배웁니다.
센서 ID를 원형 버퍼 슬롯에 매핑센서당 최신 읽기만 저장타임스탬프 필드와 단조 증가 순서덮어쓰기와 랩어라운드 케이스 처리동시식 접근을 위한 일관성 규칙수업 6init_table: 빈 마커 설정, 자유 목록 또는 토브스톤 초기화init_table 책임을 설명하며, 빈 마커 설정, 자유 목록 또는 토브스톤 초기화, 메타데이터 초기화, 첫 사용 전 일관되고 검증 가능한 상태로 테이블 시작을 보장합니다.
빈 마커 선택과 설정토브스톤과 상태 플래그 초기화초기 자유 목록 구조 구축테이블 메모리 0 초기화 또는 정화초기화 후 검증 검사수업 7insert_or_update_reading: 삽입, 업데이트, 가득 찬 테이블 처리, 반환 코드insert_or_update_reading API를 설명하며, 삽입, 현장 업데이트, 가득 찬 테이블 처리, 반환 코드, 충돌 처리를 통합하면서 C에서 간단하고 견고한 인터페이스를 유지하는 방법을 다룹니다.
함수 프로토타입과 매개변수 선택새 센서 ID 삽입 경로기존 센서 ID 업데이트 경로가득 찬 테이블과 오류 반환 처리명확한 상태와 오류 코드 설계수업 8버킷 배열 설계: 테이블 크기 선택, 소수 크기, 컴파일 타임 상수버킷 배열 설계 방법을 설명하며, 테이블 크기 선택, 소수 또는 2의 거듭제곱 크기, 컴파일 타임 상수, 메모리 사용량, 속도, 해시 함수 단순성 간 트레이드오프를 다룹니다.
소수 vs 2의 거듭제곱 테이블 크기키 용량과 테이블 크기 관계C에서 컴파일 타임 상수 사용메모리와 성능 균형미래 크기 조정 계획수업 9배열을 사용한 정적 체이닝: 노드 풀 설계, 다음 인덱스, 정적 메모리 자유 목록 관리배열을 사용한 정적 별도 체이닝을 다루며, 노드 풀 레이아웃, 다음 인덱스 링크, 자유 목록 관리, 제한된 환경에서 힙 할당 없이 삽입, 삭제, 순회를 구현하는 방법을 설명합니다.
노드 풀 배열 레이아웃 설계포인터 대신 다음 인덱스 사용정적 메모리 자유 목록 관리정적 체인 삽입과 삭제풀 소진과 오류 감지수업 10키와 값 표현: uint8_t 센서 ID와 SensorReading 복사 의미론 사용uint8_t 센서 ID와 SensorReading 구조체를 사용하여 키와 값을 표현하는 방법을 설명합니다. 복사 의미론, 정렬, 패딩, 정적 해시 테이블에서 별칭이나 수명 문제를 피하는 데 중점을 둡니다.
센서 ID 키에 uint8_t 선택SensorReading 구조체 설계복사 의미론 vs 포인터 의미론정렬, 패딩, 구조체 레이아웃센서 ID 검증과 정규화수업 11작은 키스페이스용 해시 함수 선택: 아이덴티티, 곱셈, 0–255 ID용 마스킹작은 uint8_t 키스페이스용 해시 함수를 논의하며, 아이덴티티 매핑, 곱셈 해싱, 마스킹, 0–255 센서 ID에 대한 단순성, 분포 품질, 계산 비용 균형 방법을 다룹니다.
밀집 ID 범위용 아이덴티티 해시uint8_t 키용 곱셈 해싱비트 마스킹과 테이블 인덱스 도출체계적 클러스터링 패턴 피하기샘플 데이터로 분포 테스트수업 12find_reading_by_id: 프로브 시퀀스, 발견 안됨 vs 발견 응답, 안전한 복사-아웃 패턴find_reading_by_id에 중점을 두며, 프로브 시퀀스, 발견됨과 발견 안됨 구분, 테이블에서 SensorReading 안전 복사, C에서 정의되지 않은 동작이나 오래된 데이터 노출 방지를 다룹니다.
함수 시그니처와 반환 패턴조회용 프로브 시퀀스 구현발견 안됨 vs 발견 결과 처리SensorReading 값 안전 복사-아웃오래된 또는 부분 작성 데이터 피하기
