HashMap 分析 实现

HashMap 这个集合经常用到的

1. 首先什么是hash 写一个hash算法

• 第一步简单的hash

typedef struct Entry{
    int key;
    char value;
} Entry;

extern int maxsize = 10;
//定义一个数组
Entry *values[10] = {};

//hash计算
int hash(int key,char value){
    int position = key%maxsize;
    //key相同的就覆盖了
    if(*(values+position) == NULL){
        Entry * temp = (Entry *)malloc(sizeof(Entry));
        temp->key = key;
        temp->value = value;
        *(values+position) = temp;
        return 0;
    }
    return -1;
}

分析hash 就是简单的对传递过来的key对数组长度取余
这时候有一个问题

1. 如果一个key对长度取余的时候 和原来的相同怎么办 也就是他俩占一个位置
2. 上边那种情况 如果余数相同 那可能是同一个key这个时候需要覆盖就好了

解决上边的问题

1. 我们每次进行插入的时候 需要进行查找操作 也就是这个key是不是存在

先写一个查找的方法

/**
 查看是否存在
 **/
int searchKey(int key){
    int position = key%maxsize;
    if(*(values+position) == NULL){
        return 1;
    }else{
        return 0;
    }
}

2. 如果这个key不存在 而且余数的位置已经被占用了 那我们得把他放到链表里
3. 也就是链表里存放的是取余数相同的key的元素 那也需要查找到最后一个然后插入（先不管我们的最后和java设计的一样不一样 我们先实现了这个功能再说）

//加上一个next域
typedef struct Entry{
    int key;
    char value;
    struct Entry *next;
} Entry;

/**
 判断key值是否相同
 
 **/
int isExist(int position,int key,char value){
    //先看数组里的元素是否相同 如果相同 那就直接把值替换掉就可以了
    if((*(values+position))->key == key){
        (*(values+position))->value = value;
        return 0;
    }
    //数组里的值不同 这个时候需要遍历这个链表 如果链表中的和他相同 那就替换value 如果不同插入到next域中
    Entry *p = (*(values+position))->next;
    while(1){
        if(p->key == key){
            p->value = value;
            return 0;
        }
        if(p->next != NULL)
            p=p->next;
        else
            break;
    }
    Entry *newEntry = (Entry*)malloc(sizeof(Entry));
    newEntry->key = key;
    newEntry->value = value;
    newEntry->next = NULL;
    p->next = newEntry;
    return 1;
}

到此我们就用c语言简单的实现了一个hashmap
思路就是和java中的hashmap

• 定义一个Entry key value next 这种结构
• 然后定义一个数组存放Entry
• 通过key对数组长度取余数 进行存放
• 如果key不同的情况下 余数相同 解决冲突 通过链表的形式