网站摄影设计wordpress 函数 文件

网站摄影设计,wordpress 函数 文件,IC 网站建设,怎么样在网上推广设计哈希映射 问题描述 不使用任何内建的哈希表库设计一个哈希映射#xff08;HashMap#xff09;。 实现 MyHashMap 类#xff1a; void put(int key, int value) 向哈希映射中插入键值对 (key, value)。如果键已经存在#xff0c;更新对应的值。int get(int key) 返回特定…设计哈希映射问题描述不使用任何内建的哈希表库设计一个哈希映射HashMap。实现MyHashMap类void put(int key, int value)向哈希映射中插入键值对(key, value)。如果键已经存在更新对应的值。int get(int key)返回特定的键所映射的值如果映射中不包含该键返回-1。void remove(key)如果映射中包含该键移除这个键值对。约束条件0 key, value 10^6最多调用10^4次put、get和remove方法示例输入: [MyHashMap, put, put, get, get, put, get, remove, get] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] 输出: [null, null, null, 1, -1, null, 1, null, -1] 解释: MyHashMap myHashMap new MyHashMap(); myHashMap.put(1, 1); // map {1:1} myHashMap.put(2, 2); // map {1:1, 2:2} myHashMap.get(1); // 返回 1 myHashMap.get(3); // 返回 -1未找到 myHashMap.put(2, 1); // map {1:1, 2:1} myHashMap.get(2); // 返回 1 myHashMap.remove(2); // map {1:1} myHashMap.get(2); // 返回 -1已被删除算法思路方法一数组直接寻址核心思想使用长度为10^61的整数数组索引表示键值表示对应的值特殊标记用-1表示键不存在因为value≥0方法二链地址核心思想使用桶数组存储键值对链表哈希函数key % bucketSize冲突处理链表存储冲突的键值对方法三开放地址核心思想冲突时寻找下一个空槽位代码实现方法一数组直接寻址classMyHashMap{privatestaticfinalintMAX_KEY1000000;privatestaticfinalintNOT_EXIST-1;privateint[]map;/** * 初始化哈希映射 * 使用数组直接寻址 */publicMyHashMap(){// 初始化数组所有值设为-1表示不存在mapnewint[MAX_KEY1];for(inti0;iMAX_KEY;i){map[i]NOT_EXIST;}}/** * 插入或更新键值对 * * param key 键 (0 key 10^6) * param value 值 (0 value 10^6) */publicvoidput(intkey,intvalue){map[key]value;}/** * 获取键对应的值 * * param key 要查找的键 * return 如果存在返回对应的值否则返回-1 */publicintget(intkey){returnmap[key];}/** * 删除键值对 * * param key 要删除的键 */publicvoidremove(intkey){map[key]NOT_EXIST;}}方法二链地址importjava.util.LinkedList;importjava.util.List;classMyHashMap{privatestaticfinalintBUCKET_SIZE1000;privateListEntry[]buckets;// 键值对定义privatestaticclassEntry{intkey;intvalue;Entry(intkey,intvalue){this.keykey;this.valuevalue;}}/** * 初始化哈希映射 * 使用链地址处理冲突 */SuppressWarnings(unchecked)publicMyHashMap(){// 创建桶数组每个桶是一个链表bucketsnewLinkedList[BUCKET_SIZE];for(inti0;iBUCKET_SIZE;i){buckets[i]newLinkedList();}}/** * 哈希函数计算键对应的桶索引 */privateinthash(intkey){returnkey%BUCKET_SIZE;}/** * 查找指定键在桶中的条目 */privateEntryfindEntry(intbucketIndex,intkey){ListEntrybucketbuckets[bucketIndex];for(Entryentry:bucket){if(entry.keykey){returnentry;}}returnnull;}/** * 插入或更新键值对 */publicvoidput(intkey,intvalue){intbucketIndexhash(key);EntryexistingEntryfindEntry(bucketIndex,key);if(existingEntry!null){// 键已存在更新值existingEntry.valuevalue;}else{// 键不存在添加新条目buckets[bucketIndex].add(newEntry(key,value));}}/** * 获取键对应的值 */publicintget(intkey){intbucketIndexhash(key);EntryentryfindEntry(bucketIndex,key);returnentry!null?entry.value:-1;}/** * 删除键值对 */publicvoidremove(intkey){intbucketIndexhash(key);ListEntrybucketbuckets[bucketIndex];// 遍历桶中的条目找到并删除for(inti0;ibucket.size();i){if(bucket.get(i).keykey){bucket.remove(i);return;}}}}方法三优化链地址classMyHashMap{privatestaticfinalintBUCKET_SIZE1000;privateNode[]buckets;// 链表节点定义privatestaticclassNode{intkey;intvalue;Nodenext;Node(intkey,intvalue){this.keykey;this.valuevalue;}}publicMyHashMap(){bucketsnewNode[BUCKET_SIZE];}privateinthash(intkey){returnkey%BUCKET_SIZE;}publicvoidput(intkey,intvalue){intbucketIndexhash(key);Nodeheadbuckets[bucketIndex];// 查找是否已存在该键Nodecurrenthead;while(current!null){if(current.keykey){current.valuevalue;// 更新值return;}currentcurrent.next;}// 键不存在在头部插入新节点NodenewNodenewNode(key,value);newNode.nexthead;buckets[bucketIndex]newNode;}publicintget(intkey){intbucketIndexhash(key);Nodecurrentbuckets[bucketIndex];while(current!null){if(current.keykey){returncurrent.value;}currentcurrent.next;}return-1;// 未找到}publicvoidremove(intkey){intbucketIndexhash(key);Nodeheadbuckets[bucketIndex];if(headnull){return;}// 如果要删除的是头节点if(head.keykey){buckets[bucketIndex]head.next;return;}// 在链表中查找并删除Nodecurrenthead;while(current.next!null){if(current.next.keykey){current.nextcurrent.next.next;return;}currentcurrent.next;}}}方法四双重哈希classMyHashMap{privatestaticfinalintTABLE_SIZE2069;// 质数privatestaticfinalintEMPTY-1;privatestaticfinalintDELETED-2;privateint[]keys;privateint[]values;publicMyHashMap(){keysnewint[TABLE_SIZE];valuesnewint[TABLE_SIZE];// 初始化所有槽位为空for(inti0;iTABLE_SIZE;i){keys[i]EMPTY;}}privateinthash1(intkey){returnkey%TABLE_SIZE;}privateinthash2(intkey){// 第二个哈希函数必须与TABLE_SIZE互质return1(key%(TABLE_SIZE-1));}publicvoidput(intkey,intvalue){intindexhash1(key);intstephash2(key);// 线性探测寻找空槽位或已存在的键while(keys[index]!EMPTYkeys[index]!DELETEDkeys[index]!key){index(indexstep)%TABLE_SIZE;}keys[index]key;values[index]value;}publicintget(intkey){intindexhash1(key);intstephash2(key);while(keys[index]!EMPTY){if(keys[index]key){returnvalues[index];}index(indexstep)%TABLE_SIZE;}return-1;}publicvoidremove(intkey){intindexhash1(key);intstephash2(key);while(keys[index]!EMPTY){if(keys[index]key){keys[index]DELETED;// 标记为已删除return;}index(indexstep)%TABLE_SIZE;}}}算法分析时间复杂度数组直接寻址所有操作O(1)链地址平均O(1)最坏O(n)所有键哈希到同一桶开放地址平均O(1)最坏O(n)空间复杂度数组直接寻址O(10^6)链地址O(n)n为实际存储的键值对数量开放地址O(TABLE_SIZE)测试用例publicclassTestMyHashMap{publicstaticvoidmain(String[]args){// 测试用例1标准示例MyHashMapmyHashMap1newMyHashMap();myHashMap1.put(1,1);myHashMap1.put(2,2);System.out.println(get(1): myHashMap1.get(1));// 1System.out.println(get(3): myHashMap1.get(3));// -1myHashMap1.put(2,1);// 更新值System.out.println(get(2): myHashMap1.get(2));// 1myHashMap1.remove(2);System.out.println(get(2): myHashMap1.get(2));// -1System.out.println();// 测试用例2边界值MyHashMapmyHashMap2newMyHashMap();myHashMap2.put(0,0);myHashMap2.put(1000000,1000000);System.out.println(get(0): myHashMap2.get(0));// 0System.out.println(get(1000000): myHashMap2.get(1000000));// 1000000myHashMap2.remove(0);myHashMap2.remove(1000000);System.out.println(get(0): myHashMap2.get(0));// -1System.out.println(get(1000000): myHashMap2.get(1000000));// -1System.out.println();// 测试用例3重复操作和更新MyHashMapmyHashMap3newMyHashMap();myHashMap3.put(5,10);myHashMap3.put(5,20);// 更新myHashMap3.put(5,30);// 再次更新System.out.println(get(5): myHashMap3.get(5));// 30myHashMap3.remove(5);myHashMap3.remove(5);// 重复删除System.out.println(get(5): myHashMap3.get(5));// -1myHashMap3.put(5,40);// 重新添加System.out.println(get(5): myHashMap3.get(5));// 40System.out.println();// 测试用例4空映射操作MyHashMapmyHashMap5newMyHashMap();System.out.println(get(42): myHashMap5.get(42));// -1myHashMap5.remove(42);// 删除不存在的键System.out.println(get(42): myHashMap5.get(42));// -1myHashMap5.put(42,84);System.out.println(get(42): myHashMap5.get(42));// 84}}关键点哈希函数简单取模key % bucketSize桶数量通常选择质数双重哈希使用两个哈希函数避免聚集冲突处理链地址每个桶维护一个链表存储键值对开放地址冲突时寻找下一个空槽位删除标记开放地址中删除需要特殊标记DELETED更新如果键已存在更新对应的值而不是添加新条目链地址需要遍历链表查找已存在的键常见问题为什么链地址比开放地址更容易实现删除链地址中删除就是从链表中移除节点不影响其他元素的查找开放地址中删除一个元素后如果设为空会导致后续元素无法被找到