---
generated_at: 2026-01-21 12:00:00
metrics:
  claims_total: 28
  claims_with_evidence: 28
  claims_without_evidence: 0
confidence_derived: 1.00
---

# 根拠レポート: 47-ハッシュテーブル

## 概要

本レポートは「機能設計書 47-ハッシュテーブル」に記載された内容の根拠を示し、各主張がソースコードのどの部分に基づいているかを明確にする。

## 根拠一覧

### 1. sqlite3HashInit関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 23-29 | `void sqlite3HashInit(Hash *pNew){ assert( pNew!=0 ); pNew->first = 0; pNew->count = 0; pNew->htsize = 0; pNew->ht = 0; }` |
| first=0で初期化 | src/hash.c | 25 | `pNew->first = 0;` |
| count=0で初期化 | src/hash.c | 26 | `pNew->count = 0;` |
| htsize=0で初期化 | src/hash.c | 27 | `pNew->htsize = 0;` |
| ht=0で初期化 | src/hash.c | 28 | `pNew->ht = 0;` |

### 2. sqlite3HashClear関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 35-50 | `void sqlite3HashClear(Hash *pH){...}` |
| ht配列の解放 | src/hash.c | 41 | `sqlite3_free(pH->ht);` |
| 全要素の解放ループ | src/hash.c | 44-48 | `while( elem ){ HashElem *next_elem = elem->next; sqlite3_free(elem); elem = next_elem; }` |

### 3. strHash関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| Knuth乗算ハッシュの説明 | src/hash.c | 58-60 | `Knuth multiplicative hashing. (Sorting & Searching, p. 510). 0x9e3779b1 is 2654435761 which is the closest prime number to (2**32)*golden_ratio` |
| 大文字小文字無視（0xDF） | src/hash.c | 62-63 | `Only bits 0xdf for ASCII and bits 0xbf for EBCDIC each octet are hashed since the omitted bits determine the upper/lower case difference.` |
| 0xDFマスクの実装 | src/hash.c | 68 | `h += 0xdf & (unsigned char)*(z++);` |
| 0x9e3779b1での乗算 | src/hash.c | 70 | `h *= 0x9e3779b1;` |
| EBCDIC対応（0xBF） | src/hash.c | 65-66 | `#ifdef SQLITE_EBCDIC h += 0xbf & (unsigned char)*(z++);` |

### 4. findElementWithHash関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 153-183 | `static HashElem *findElementWithHash(const Hash *pH, const char *pKey, unsigned int *pHash){...}` |
| nullElement静的変数 | src/hash.c | 161 | `static HashElem nullElement = { 0, 0, 0, 0, 0 };` |
| strHashでハッシュ計算 | src/hash.c | 163 | `h = strHash(pKey);` |
| htがあればバケット検索 | src/hash.c | 164-168 | `if( pH->ht ){ struct _ht *pEntry; pEntry = &pH->ht[h % pH->htsize]; elem = pEntry->chain; count = pEntry->count; }` |
| htがなければ全体検索 | src/hash.c | 169-172 | `else{ elem = pH->first; count = pH->count; }` |
| ハッシュとキーの両方を比較 | src/hash.c | 176 | `if( h==elem->h && sqlite3StrICmp(elem->pKey,pKey)==0 ){` |
| 見つからなければnullElement返却 | src/hash.c | 182 | `return &nullElement;` |

### 5. insertElement関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 79-104 | `static void insertElement(Hash *pH, struct _ht *pEntry, HashElem *pNew){...}` |
| バケットのcountインクリメント | src/hash.c | 87 | `pEntry->count++;` |
| バケットのchainに設定 | src/hash.c | 88 | `pEntry->chain = pNew;` |
| 双方向リスト操作 | src/hash.c | 92-103 | リスト挿入ロジック |

### 6. removeElement関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 188-216 | `static void removeElement(Hash *pH, HashElem *elem){...}` |
| 双方向リストからの削除 | src/hash.c | 193-200 | prevとnextの付け替え |
| バケットのcount減算 | src/hash.c | 207 | `pEntry->count--;` |
| 要素の解放 | src/hash.c | 209 | `sqlite3_free( elem );` |
| count==0でHashClear | src/hash.c | 211-214 | `if( pH->count==0 ){ assert( pH->first==0 ); assert( pH->count==0 ); sqlite3HashClear(pH); }` |

### 7. sqlite3HashFind関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 222-226 | `void *sqlite3HashFind(const Hash *pH, const char *pKey){ assert( pH!=0 ); assert( pKey!=0 ); return findElementWithHash(pH, pKey, 0)->data; }` |

### 8. sqlite3HashInsert関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 242-272 | `void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){...}` |
| 既存要素の検索 | src/hash.c | 249 | `elem = findElementWithHash(pH,pKey,&h);` |
| data==NULLで削除 | src/hash.c | 252-253 | `if( data==0 ){ removeElement(pH,elem); }` |
| dataで更新 | src/hash.c | 254-256 | `else{ elem->data = data; elem->pKey = pKey; }` |
| 旧dataを返却 | src/hash.c | 258 | `return old_data;` |
| HashElem確保 | src/hash.c | 261 | `new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );` |
| malloc失敗時dataを返却 | src/hash.c | 262 | `if( new_elem==0 ) return data;` |
| リハッシュ条件 | src/hash.c | 267 | `if( pH->count>=5 && pH->count > 2*pH->htsize ){` |
| リハッシュサイズcount*3 | src/hash.c | 268 | `rehash(pH, pH->count*3);` |

### 9. rehash関数に関する根拠

| 主張 | 根拠ファイル | 該当行 | 根拠コード/コメント |
|------|-------------|--------|-------------------|
| 関数定義 | src/hash.c | 113-146 | `static int rehash(Hash *pH, unsigned int new_size){...}` |
| SQLITE_MALLOC_SOFT_LIMIT制限 | src/hash.c | 117-121 | `#if SQLITE_MALLOC_SOFT_LIMIT>0 if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){ new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht); }` |
| 良性mallocとしての処理 | src/hash.c | 132-134 | `sqlite3BeginBenignMalloc(); new_ht = (struct _ht *)sqlite3Malloc(...); sqlite3EndBenignMalloc();` |
| sqlite3MallocSizeで実サイズ取得 | src/hash.c | 139 | `pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht);` |
| 全要素の再配置 | src/hash.c | 141-144 | `for(elem=pH->first, pH->first=0; elem; elem = next_elem){ next_elem = elem->next; insertElement(pH, &new_ht[elem->h % new_size], elem); }` |

## 根拠なし項目

なし

## 信頼度評価

- **claims_total**: 28
- **claims_with_evidence**: 28
- **claims_without_evidence**: 0
- **confidence_derived**: 28 / 28 = 1.00 (100%)

すべての主張についてソースコード内に明確な根拠が存在する。
