面試算法題：十億用戶名去重最優解法與 C/C++ 實作

題目描述

兩個日誌檔，各含 10 億用戶名，找出同時存在於兩檔的用戶名。要求最高效率，C/C++ 實作，庫函數需從零手寫。

解決方案：位圖哈希表

記憶體限制下不可存儲完整字串。採用位陣列 + 自定義哈希：

1. 申請 1億位 (≈12.5MB) 位圖 hashMap，初始化為 0
2. 讀檔 1：用戶名 → 哈希碼 → 位圖對應位置 1
3. 讀檔 2：用戶名 → 哈希碼 → 檢查位圖位，為 1 則輸出

哈希函數設計

字元加權累加：字母按 (字元-'A')*(位置+1)，數字按 (字元-'0')*(位置+1)，降低碰撞。

核心代碼片段

#define BITSPERWORD 32
#define N 100000000
int hashMap[1 + N/BITSPERWORD];

void set(int i) { hashMap[i/32] |= (1<<(i%32)); }
void clr() { memset(hashMap,0,sizeof(hashMap)); }
int test(int i) { return hashMap[i/32] & (1<<(i%32)); }

void hash_code(char *src, int *hash) {
    int sum=0, idx=0;
    while(*src) {
        idx++;
        if(isalpha(*src)) sum += idx * (*src - 'A');
        else if(isdigit(*src)) sum += idx * (*src - '0');
        src++;
    }
    *hash = sum;
}

完整代碼含檔案讀寫、主流程控制。面試後獲邀但薪資不符期望婉拒，引發對開發者價值的思考。

來源：雨落孤林博客