资讯专栏INFORMATION COLUMN

[LeetCode] 706. Design HashMap

bergwhite / 455人阅读

Problem

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);
hashMap.put(2, 2);
hashMap.get(1); // returns 1
hashMap.get(3); // returns -1 (not found)
hashMap.put(2, 1); // update the existing value
hashMap.get(2); // returns 1
hashMap.remove(2); // remove the mapping for 2
hashMap.get(2); // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].
The number of operations will be in the range of [1, 10000].
Please do not use the built-in HashMap library.

Solution

</>复制代码

  1. class MyHashMap {
  2. class ListNode {
  3. ListNode next;
  4. int key, val;
  5. ListNode(int key, int value) {
  6. this.key = key;
  7. this.val = value;
  8. }
  9. }
  10. class Bucket {
  11. final ListNode head = new ListNode(-1, -1);
  12. }
  13. final int size = 10000;
  14. final Bucket[] buckets = new Bucket[size];
  15. /** Initialize your data structure here. */
  16. public MyHashMap() {
  17. }
  18. //used to find the bucket
  19. private int hash(int key) {
  20. return key % size;
  21. }
  22. //used to find node by key in certain bucket
  23. private ListNode findNode(Bucket bucket, int key) {
  24. ListNode head = bucket.head;
  25. ListNode node = head;
  26. while (head != null && head.key != key) {
  27. //when head == null, or head.key == key, return its previous node
  28. node = head;
  29. head = head.next;
  30. }
  31. return node;
  32. }
  33. /** value will always be non-negative. */
  34. public void put(int key, int value) {
  35. int i = hash(key);
  36. if (buckets[i] == null) buckets[i] = new Bucket();
  37. ListNode pre = findNode(buckets[i], key);
  38. if (pre.next == null) {
  39. pre.next = new ListNode(key, value);
  40. } else {
  41. pre.next.val = value;
  42. }
  43. }
  44. /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
  45. public int get(int key) {
  46. int i = hash(key);
  47. if (buckets[i] == null) return -1;
  48. ListNode pre = findNode(buckets[i], key);
  49. if (pre.next == null) {
  50. return -1;
  51. } else {
  52. return pre.next.val;
  53. }
  54. }
  55. /** Removes the mapping of the specified value key if this map contains a mapping for the key */
  56. public void remove(int key) {
  57. int i = hash(key);
  58. if (buckets[i] == null) return;
  59. ListNode pre = findNode(buckets[i], key);
  60. if (pre.next == null) return;
  61. else pre.next = pre.next.next;
  62. }
  63. }
  64. /**
  65. * Your MyHashMap object will be instantiated and called as such:
  66. * MyHashMap obj = new MyHashMap();
  67. * obj.put(key,value);
  68. * int param_2 = obj.get(key);
  69. * obj.remove(key);
  70. */

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/77182.html

相关文章

  • Leetcode PHP题解--D75 706. Design HashMap

    摘要:题目链接题目分析自行设计一个。需要实现题目内指定的函数。思路我觉得这个没什么好说的吧最终代码若觉得本文章对你有用,欢迎用爱发电资助。 D75 706. Design HashMap 题目链接 706. Design HashMap 题目分析 自行设计一个hashmap。 需要实现题目内指定的函数。 思路 我觉得这个没什么好说的吧… 最终代码

    sf190404 评论0 收藏0
  • 359. Logger Rate Limiter & 362. Design Hit Cou

    摘要:题目链接和基本一样,都可以用,但是大了之后会有很多无效的时间保存在里面,要的话,可能需要遍历或者用辅助,时间复杂度超过,所以用一个来做,每次根据新的改变。 359. Logger Rate Limiter 题目链接:https://leetcode.com/problems... 和Design Hit Counter基本一样,都可以用hashmap,但是timestamp大了之后会有...

    go4it 评论0 收藏0
  • [LeetCode] 642. Design Search Autocomplete System

    Problem Design a search autocomplete system for a search engine. Users may input a sentence (at least one word and end with a special character #). For each character they type except #, you need to r...

    MartinHan 评论0 收藏0
  • [LeetCode/LintCode] Design Twitter/Mini Twitter

    摘要:首先建立按时间戳从大到小排列的,找到中的,出其中在中存在的,把每一个的推特链表放入,再从中取头十条推特的放入结果数组。 Design Twitter Note 建立两个HashMap,一个存user,一个存tweets。以及整型的时间戳timestamp。user的k-v pair是userId-follower_set,tweets的k-v pair是userId-tweets_li...

    honmaple 评论0 收藏0
  • [LeetCode] 588. Design In-Memory File System

    Problem Design an in-memory file system to simulate the following functions: ls: Given a path in string format. If it is a file path, return a list that only contains this files name. If it is a direc...

    SHERlocked93 评论0 收藏0

发表评论

0条评论

bergwhite

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<