奇梦者科技 C++开发 一面

1. 全局变量、局部变量、静态变量分别存在哪里，如果不初始化默认是什么值

答案：全局变量和静态变量如果是已初始化的，一般放在数据段；如果未显式初始化，通常放在 BSS 段。局部变量一般放在栈上，函数调用结束后生命周期就结束。static 修饰的局部变量，存储位置不在栈上，而是在静态存储区，只是作用域仍然限定在函数内部。默认初始化这块要分清楚：全局变量、静态变量、静态局部变量如果没有显式初始化，默认会被置为 0；普通局部变量如果没初始化，值是不确定的，直接用属于未定义行为。

代码：

#include <stdio.h>

int g1;           // BSS，默认 0
int g2 = 10;      // 数据段
static int s1;    // BSS，默认 0

void test() {
    int a;                // 栈上，未初始化，值不确定
    static int b;         // 静态存储区，默认 0
    printf("b = %d\n", b);
    b++;
}

int main() {
    printf("g1 = %d, g2 = %d, s1 = %d\n", g1, g2, s1);
    test();
    test();
    return 0;
}

2. 堆和栈的区别是什么

答案：栈通常由编译器和运行时自动管理，主要存函数调用现场、局部变量、返回地址，分配和释放都很快，但空间相对小。堆由程序员或内存分配器动态管理，适合生命周期不固定、大小运行期才能确定的数据，灵活性高，但分配释放开销更大，也更容易产生碎片和泄漏。栈上的数据生命周期跟作用域绑定，函数退出基本就没了；堆上的对象要靠 malloc/free 或 new/delete 主动管理。另外栈是向低地址还是高地址增长、堆如何扩展，这些是实现相关的，但常见系统里栈和堆是相向增长的。

代码：

#include <stdio.h>
#include <stdlib.h>

void func() {
    int x = 10;                  // 栈
    int *p = (int*)malloc(sizeof(int)); // 堆
    *p = 20;
    printf("%d %d\n", x, *p);
    free(p);
}

3. 除了堆和栈，进程地址空间里通常还有哪些区域

答案：一个进程的虚拟地址空间里通常不只有代码段、数据段、BSS、堆、栈，还会有共享库映射区、匿名映射区、只读常量区、内核空间映射等。代码段一般放程序指令，常量字符串通常在只读区。堆用于动态分配，栈用于函数调用。共享库比如 libc 会通过 mmap 映射到进程地址空间，文件映射、共享内存、大块内存分配也常常走映射区。如果再深一点，线程还会有各自独立的用户栈和线程局部存储区。

4. 哈希函数主要解决什么问题

哈希函数的核心作用是把一个范围很大的 key，映射成一个相对固定范围内的整数下标，方便快速存储和查找。它解决的不是“排序”问题，而是“如何尽量快地定位数据”问题。理想情况下，希望不同 key 经过哈希后分布尽量均匀，这样哈希表的插入、查找、删除平均复杂度可以做到 O(1)。但哈希函数不能避免冲突，只能尽量减少冲突，所以哈希表还要有冲突处理机制，比如拉链法、开放寻址法。如果哈希函数设计得很差，数据大量聚集到少数桶里，性能就会明显退化。

代码：

unsigned int hash(const char *s) {
    unsigned int h = 0;
    while (*s) {
        h = h * 131 + (unsigned char)(*s++);
    }
    return h;
}

5. 哈希冲突一般怎么处理，扩容时会发生什么

答案：哈希冲突指的是不同 key 经过哈希后映射到了同一个位置。常见处理方式有两类，一类是拉链法，也就是每个桶挂一个链表或者其他容器；另一类是开放寻址，比如线性探测、二次探测。工业里很多语言和库的哈希表会优先考虑拉链法或者拉链法的变种，因为删除和扩展更自然。当负载因子变高，冲突增多时，哈希表通常会扩容。扩容不是简单把数组变大，还要把原来所有元素重新计算桶位置，这个过程叫 rehash。所以平时说哈希表平均 O(1)，前提是负载因子控制得当，哈希函数分布也比较均匀。

6. C 语言实现一个 value 为字符串的哈希表，怎么设计

用 C 实现哈希表，一般要先定义节点结构体，里面至少有 key、value 和冲突链指针。底层可以用桶数组加链表，也就是拉链法。查找时先算桶下标，再在链表里比较 key；插入时如果 key 已存在就更新，不存在就头插新节点。如果 value 是字符串，要注意内存所有权，不能直接拿外部临时指针乱存，通常要自己 strdup 或者手动申请空间复制。删除时除了摘链表，还要记得释放 key 和 value 对应的内存。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 101

typedef struct Node {
    char *key;
    char *value;
    struct Node *next;
} Node;

typedef struct {
    Node *buckets[TABLE_SIZE];
} HashTable;

unsigned int hash(const char *s) {
    unsigned int h = 0;
    while (*s) h = h * 131 + (unsigned char)(*s++);
    return h % TABLE_SIZE;
}

char *my_strdup(const char *s) {
    size_t n = strlen(s);
    char *p = (char*)malloc(n + 1);
    if (p) strcpy(p, s);
    return p;
}

void put(HashTable *ht, const char *key, const char