推荐系统中的 Hash 与位运算技巧：从 CityHash 到 Feature Hashing

1
2
3
4

#include <city.h>

// 包装宏：字符串 → uint64_t
#define MAKE_HASH(str) CityHash64((str).c_str(), (str).size())

1
2
3
4
5
6
7
8

// 项目里 LRU Cache 的哈希委托给 std::hash
namespace std {
  template<> struct hash<CacheItem> {
    size_t operator()(const CacheItem& item) const {
      return hash<string>()(item.key);
    }
  };
}

1
2
3
4
5

// 二特征交叉：左移 1 位后与第二个哈希异或
#define GEN_HASH2(h1, h2) (((h1) << 1) ^ (h2))

// 三特征交叉：级联 GEN_HASH2
#define GEN_HASH3(h1, h2, h3) (((GEN_HASH2(h1, h2)) << 1) ^ (h3))

1
2
3
4

// Boost 的经典哈希组合函数
size_t hash_combine(size_t seed, size_t value) {
  return seed ^ (value + 0x9e3779b9 + (seed << 6) + (seed >> 2));
}

1

#define HASH_FEATURE_ID(_id_) (_id_) + kHashFeatureOffset  // +1,000,000

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// 1. 特征名 → CityHash → 特征 ID 哈希
uint64_t id_hash = MAKE_HASH(feature_name);

// 2. 组合特征值（笛卡尔积）
for (auto v1 : values1) {
  for (auto v2 : values2) {
    uint64_t combined = GEN_HASH2(v1, v2);
    // 3. 最终 LR 特征 = 特征ID哈希 与 组合值哈希 再混合
    uint64_t final_hash = GEN_HASH2(id_hash, combined);
    // 4. 加上偏移，输出给模型
    int64_t feature_id = HASH_FEATURE_ID(final_hash);
  }
}

1
2
3

// 随机退避 0~1023 ms，避免所有 consumer 同时重连
uint32_t backoff_ms = rand() & 1023;
std::this_thread::sleep_for(std::chrono::milliseconds(backoff_ms));

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// 定义标志（每个标志占一位）
#define FLAG_A (1 << 0)   // 0b0001
#define FLAG_B (1 << 1)   // 0b0010
#define FLAG_C (1 << 2)   // 0b0100

// 设置标志
flags |= FLAG_A;          // 0001

// 检测标志
if (flags & FLAG_A) { }   // 判断第 0 位是否为 1

// 切换标志（1→0, 0→1）
flags ^= FLAG_A;          // XOR 特性：a ^ a = 0

// 组合标志
#define COMBO (FLAG_A | FLAG_B)   // 0b0011

// 清除标志（只保留特定位）
flags &= MASK;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// TinyXML2 的节点标志
enum {
  NEEDS_ENTITY_PROCESSING   = 0x01,
  NEEDS_NEWLINE_NORMALIZATION = 0x02,
  NEEDS_WHITESPACE_COLLAPSING = 0x04,
  TEXT_ELEMENT              = NEEDS_ENTITY_PROCESSING | NEEDS_NEWLINE_NORMALIZATION
};

// 检测是否需要刷新
if (node->flags & NEEDS_FLUSH) { ... }

// 关闭 flush 标志
node->flags ^= NEEDS_FLUSH;

1
2
3
4
5
6
7
8
9

#include <sys/stat.h>

struct stat st;
stat(path.c_str(), &st);

// 判断是否为普通文件（位掩码）
if ((st.st_mode & S_IFREG) == S_IFREG) {
  // 是普通文件
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// 假设 input 是 Unicode 码点（32位）
// 1. 先填充 continuation bytes（从低 6 位开始）
for (int i = 3; i >= 0; --i) {
  if (input >> (6 * i)) {
    // 设置 continuation byte 标记：10xxxxxx
    unsigned char c = (input | 0x80) & 0xBF;  // 0x80=10000000, 0xBF=10111111
    // ...
    input >>= 6;  // 右移 6 位，处理下一个片段
  }
}

// 2. 设置首字节前缀
// 1字节: 0xxxxxxx
// 2字节: 110xxxxx
// 3字节: 1110xxxx
// 4字节: 11110xxx
input |= FIRST_BYTE_MARK[len];

1
2
3
4
5
6
7
8

// common/common_define.h
#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)

// 使用场景
if (unlikely(ptr == nullptr)) {  // 告诉编译器：这个分支很少发生
  return Status::NullPointer;
}