Android BlueDroid分析: OSI中的HashMap的实现

2024-03-04 12:18
文章标签 分析 实现 android hashmap osi bluedroid

本文主要是介绍Android BlueDroid分析: OSI中的HashMap的实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

说明

hash map在C语言标准库中并没有封装, 不像其他语言那么方便, 例如python中有Dictionary, 而hashmap又非常有用, 因此Bluedroid自己封装了一套.封装实现的文件列表如下:

osi/src/hash_functions.c  
osi/src/hash_map.c
osi/include/hash_functions.h
osi/include/hash_map.h
其中hash_functions.c中是对几个 特殊类型的hashmap封装. 因此我们先说明hash map, 然后再看hash functions.

HashMap概念与术语

首先如果要实现hashmap,那么需要做什么呢? 下面是引用StackOverFlow中的回答:

Well if you know the basics behind them, it shouldn't be too hard.Generally you create an array called "buckets" that contain the key and value, with an optional pointer to create a linked list.When you access the hash table with a key, you process the key with a custom hash function which will return an integer. You then take the modulus of the result and that is the location of your array index or "bucket". Then you check the unhashed key with the stored key, and if it matches, then you found the right place.Otherwise, you've had a "collision" and must crawl through the linked list and compare keys until you match. (note some implementations use a binary tree instead of linked list for collisions).Check out this fast hash table implementation:http://attractivechaos.awardspace.com/khash.h.html

简单来说就是:

  • A1. 创建: 创建一个数组bucket,其中bucket包含有key value对, 还有一个可选的list指针
  • A2. 访问查询: 使用key来查询时, 先将key转换(通过自定义的转换函数)成一个整数, 然后取模得到一个数, 再使用这个数到bucket(或者数组对应下表元素)查找是否有相同的key.如果有且只有一个的话,那么就找到了.
  • A3. 如果一个key找到value的list不为空,即有发生了哈希冲突,那么就需要遍历List中的所有元素.

上面的取模仅仅只是其中的一种哈希函数(散列函数), 可以参考下面文章中的说明:哈希表的C实现(一)

关于hash冲突(Hash collision), 也可以参考上面链接中的说明.下面是其中的链接地址法的引用:

链地址法：举例说明： 设有 8 个元素 { a,b,c,d,e,f,g,h } ，采用某种哈希函数得到的地址分别为： {0 ， 2 ， 4 ， 1 ， 0 ， 8 ， 7 ， 2} ，当哈希表长度为 10 时，采用链地址法解决冲突的哈希表如下图所示。


                 (下面文中说的前面图中,均指这个图片)


结合这个图片来说, 前面的A2与A3这两个步骤就是横向与纵向的查找,先是纵向的查找(0~8, bucket), 然后如果有冲突, 例如index=0的就有a与e两个, 这个时候就再横向的List遍历查找.

对于哈希冲突还有另一种使用表来完成的做法可以参考: 哈希桶的分析与实现

结构定义

结合前面的说明,对于代码中的桶的定义也就很容易看明白了. 可以认为每一个hash都是由下面这个hash_map_entry来表示的, 这个是最小的单元,含有key value(这里面为*data指针)对.

typedef struct hash_map_entry_t {const void *key;void *data;const hash_map_t *hash_map;  // 指向所在的hash_map
} hash_map_entry_t;

hash_map_bucket_t:为list指针, 即前面图中的横向结构

hash_map_t

struct hash_map_t;typedef struct hash_map_bucket_t {list_t *list;              // 链表指针,表示
} hash_map_bucket_t;typedef struct hash_map_t {hash_map_bucket_t *bucket;  // 是一个指向list*的指针, 即相当于List指针数组size_t num_bucket;          // 有多少个entry, 即相当于前面图中的纵向元素.size_t hash_size;           // 有多少个hash元素(key/value对),即为前面图中的横向所有List中的hash总数
																														//   这个统计的是前面的hash_map_entry_t元素hash_index_fn hash_fn;      // 获取取模强的整数函数key_free_fn key_fn;         data_free_fn data_fn;const allocator_t *allocator;key_equality_fn keys_are_equal; //key的判断函数,即前面A1中说到的自定义的equal判断函数指针
} hash_map_t;

hash的各种功能函数

hash_map.c中的information如下, 其中我们需要注意的是new/clear/free, 然后使用的时候会有set/erase,查询的时候是get/empty/size/has_key:

查找是否有key这个/条item

第一步和前面说的A1是对应的,先取模获取index, 然后根据index作为数组下标获取bucket的List, 然后再到List中遍历:

bool hash_map_has_key(const hash_map_t *hash_map, const void *key) {assert(hash_map != NULL);hash_index_t hash_key = hash_map->hash_fn(key) % hash_map->num_bucket;list_t *hash_bucket_list = hash_map->bucket[hash_key].list;hash_map_entry_t *hash_map_entry = find_bucket_entry_(hash_bucket_list, key);return (hash_map_entry != NULL);
}

里面的find_bucket_entry_, 即为前面A3步骤的函数实现为find_bucket_entry_, 传入的参数为List + key:

static hash_map_entry_t * find_bucket_entry_(list_t *hash_bucket_list,const void *key) {if (hash_bucket_list == NULL)return NULL;for (const list_node_t *iter = list_begin(hash_bucket_list);iter != list_end(hash_bucket_list);iter = list_next(iter)) {hash_map_entry_t *hash_map_entry = (hash_map_entry_t *)list_node(iter);if (hash_map_entry->hash_map->keys_are_equal(hash_map_entry->key, key)) {return hash_map_entry;}}return NULL;
}

向hashmap中插入一个key/value Pair

下面是函数以及注释

bool hash_map_set(hash_map_t *hash_map, const void *key, void *data) {assert(hash_map != NULL);assert(data != NULL);hash_index_t hash_key = hash_map->hash_fn(key) % hash_map->num_bucket; //哈希函数获取Index整数, 即得到前面图中纵向的入口// 如果这个key还不存在,那么创建一个List Entry,即图中纵向创建一个Entryif (hash_map->bucket[hash_key].list == NULL) {hash_map->bucket[hash_key].list = list_new_internal(bucket_free_, hash_map->allocator);if (hash_map->bucket[hash_key].list == NULL)return false;}list_t *hash_bucket_list = hash_map->bucket[hash_key].list; //获取横向的List用于相同key的操作hash_map_entry_t *hash_map_entry = find_bucket_entry_(hash_bucket_list, key);//已经存在相同的值了, 那么先remove掉原来的,然后覆盖进去if (hash_map_entry) {// Calls hash_map callback to delete the hash_map_entry.bool rc = list_remove(hash_bucket_list, hash_map_entry);assert(rc == true);} else { // 还不存在,先增加hash element的计数hash_map->hash_size++; }hash_map_entry = hash_map->allocator->alloc(sizeof(hash_map_entry_t)); //为存放key/value即元素分配空间if (hash_map_entry == NULL)return false;// 完成element的填充hash_map_entry->key = key;hash_map_entry->data = data;hash_map_entry->hash_map = hash_map;// 将这个hash元素追加到list中,完成添加工作return list_append(hash_bucket_list, hash_map_entry);
}
弄明白了这两个函数后其他函数都比较容易了, 就不再贴出.

hash_functions.c的分析

前面是hashmap的实现分析, 里面实现了对hash的创建查询等, 而hash_functions.c中则是对一些特别的类型的进行的一些key的预分配, 这个如何Linux Driver中的DMA与CMA很类似, 相当于特殊化几个key地址值, 而这个特殊化和Linux中的线性映射区Physical Address到Virtual Memory Address的很类似(这里面由+0xX0000000的偏移,变成了乘以某个数值), :

#include "osi/include/hash_functions.h"hash_index_t hash_function_naive(const void *key) {return (hash_index_t)key;
}
// 对于Interger与pointer将key的地址值特殊化, 
hash_index_t hash_function_integer(const void *key) {return ((hash_index_t)key) * 2654435761;
}hash_index_t hash_function_pointer(const void *key) {return ((hash_index_t)key) * 2654435761;
}hash_index_t hash_function_string(const void *key) {hash_index_t hash = 5381;const char *name = (const char *)key;size_t string_len = strlen(name);for (size_t i = 0; i < string_len; ++i)hash = ((hash << 5) + hash ) + name[i];return hash;
}

例如: 

bta_alarm_hash_map = hash_map_new(BTA_ALARM_HASH_MAP_SIZE,hash_function_pointer, NULL, (data_free_fn)alarm_free, NULL);

hash_map_new的实现为: 

hash_map_t *hash_map_new(size_t num_bucket,hash_index_fn hash_fn,key_free_fn key_fn,data_free_fn data_fn,key_equality_fn equality_fn) {return hash_map_new_internal(num_bucket, hash_fn, key_fn, data_fn, equality_fn, &allocator_calloc);
}

即: hash_index_fn = hash_function_pointer. 这个有什么用处呢?

例如刚刚给出的这个例子位于:bta_sys_main.c中, 其使用如下:

void bta_sys_start_timer(TIMER_LIST_ENT *p_tle, UINT16 type, INT32 timeout_ms) {assert(p_tle != NULL);// Get the alarm for this p_tle.pthread_mutex_lock(&bta_alarm_lock);if (!hash_map_has_key(bta_alarm_hash_map, p_tle)) {hash_map_set(bta_alarm_hash_map, p_tle, alarm_new());//p_tle为key,new了一个alarm放在这个key对应的List上面}pthread_mutex_unlock(&bta_alarm_lock);alarm_t *alarm = hash_map_get(bta_alarm_hash_map, p_tle);if (alarm == NULL) {LOG_ERROR("%s unable to create alarm.", __func__);return;}p_tle->event = type;p_tle->ticks = timeout_ms;alarm_set(alarm, (period_ms_t)timeout_ms, bta_alarm_cb, p_tle);
}

这里p_tle为key, 有一组的timer在这个key对应的List的element上, 假设HCI下面的Controller的buffer size很大,即可以发送与处理多条commands, 那么Host需要等待这些commands的Event回来, 那么每个commands发送完成后都有一个timer定时,这些timer均相关, 那么就可以用这种方式来管理.

这篇关于Android BlueDroid分析: OSI中的HashMap的实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/773139。

相关文章

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯，先赞后看哦~🎈🎈 🏆 作者简介：景天科技苑 🏆《头衔》：大厂架构师，华为云开发者社区专家博主，阿里云开发者社区专家博主，CSDN全栈领域优质创作者，掘金优秀博主，51CTO博客专家等。 🏆《博客》：Python全栈，前后端开发，小程序开发，人工智能，js逆向，App逆向，网络系统安全，数据分析，Django，fastapi
阅读更多...
让树莓派智能语音助手实现定时提醒功能

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现，因为rasa本身是带有remindschedule模块的。不过经过一番折腾后，忽然发现，chatbot上实现的定时，语音助手不一定会有响应。因为，我目前语音助手的代码设置了长时间无应答会结束对话，这样一来，chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢？ 我最后选择的方法是用threading.Time
阅读更多...
Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸（两张壁纸可不一致）

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸： 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  （注意不能是bmp格式） 替换默认锁屏壁纸： 将图片资源放入vendo
阅读更多...
C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

C#实战|大乐透选号器[6]：实现实时显示已选择的红蓝球数量

哈喽，你好啊，我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记，这是第6篇； 接下来实现实时显示当前选中红球数量，蓝球数量； 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时，在对应的位置显示实时已选择的红球、蓝球的数量； 02 标签名称 分别设置Label标签名称为：lblRedCount、lblBlueCount
阅读更多...
Android平台播放RTSP流的几种方案探究（VLC VS ExoPlayer VS SmartPlayer）

Android平台播放RTSP流的几种方案探究（VLC VS ExoPlayer VS SmartPlayer）

技术背景 好多开发者需要遴选Android平台RTSP直播播放器的时候，不知道如何选的好，本文针对常用的方案，做个大概的说明： 1. 使用VLC for Android VLC Media Player（VLC多媒体播放器），最初命名为VideoLAN客户端，是VideoLAN品牌产品，是VideoLAN计划的多媒体播放器。它支持众多音频与视频解码器及文件格式，并支持DVD影音光盘，VCD影
阅读更多...
Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略

Kubernetes PodSecurityPolicy：PSP能实现的5种主要安全策略 1. 特权模式限制2. 宿主机资源隔离3. 用户和组管理4. 权限提升控制5. SELinux配置 💖The Begin💖点点关注，收藏不迷路💖 Kubernetes的PodSecurityPolicy（PSP）是一个关键的安全特性，它在Pod创建之前实施安全策略，确保P
阅读更多...
SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

SWAP作物生长模型安装教程、数据制备、敏感性分析、气候变化影响、R模型敏感性分析与贝叶斯优化、Fortran源代码分析、气候数据降尺度与变化影响分析

查看原文>>>全流程SWAP农业模型数据制备、敏感性分析及气候变化影响实践技术应用 SWAP模型是由荷兰瓦赫宁根大学开发的先进农作物模型，它综合考虑了土壤-水分-大气以及植被间的相互作用；是一种描述作物生长过程的一种机理性作物生长模型。它不但运用Richard方程，使其能够精确的模拟土壤中水分的运动，而且耦合了WOFOST作物模型使作物的生长描述更为科学。 本文让更多的科研人员和农业工作者
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2