loserwang

loserwang 查看完整档案

填写现居城市  |  填写毕业院校  |  填写所在公司/组织填写个人主网站
编辑
_ | |__ _ _ __ _ | '_ \| | | |/ _` | | |_) | |_| | (_| | |_.__/ \__,_|\__, | |___/ 该用户太懒什么也没留下

个人动态

loserwang 提出了问题 · 10月20日

ant design表格render函数中text和record参数的区别?

函数说明
renderfunction(text, record, index)生成复杂数据的渲染函数,参数分别为当前行的值,当前行数据,行索引,

text和record分别是什么?为什么我打印出来的结果一样?

关注 2 回答 1

loserwang 回答了问题 · 10月17日

数据库的锁机制和事务经常配合一起用吗?对他们有点模糊不清了

锁只是为了保证多个事务并发执行一致性的一种手段,并发一致性也可以通过时间戳等手段实现。

关注 4 回答 2

loserwang 提出了问题 · 10月16日

数据库两段封锁协议能解决脏读么?

数据库中的两段封锁协议的规则是先加锁,后解锁,所以可以保证冲突可串行化,来保证并发的一致性。
但是两段封锁协议并不满足一级协议(即在事务commit时释放锁)。如果:事务1 修改数据A和B, 事务2 修改数据B. 事务1先获取A和B的锁,修改A的值,然后释放A的锁。在事务2获取A的锁的同时,如果事务1修改B失败,要进行roll back, 会发生什么?事务2 是否对A数据脏读?

关注 1 回答 0

loserwang 收藏了问题 · 10月15日

Spring父容器与Spring MVC子容器是如何体现出父子关系的

平常的子类继承父类通过extends关键字来实现,那么Spring父容器与Spring MVC子容器是如何体现出父子关系的呢?
容器指的是一个类吗?Spring容器是哪个类,Spring MVC容器又是哪个类?

loserwang 赞了回答 · 10月15日

Spring父容器与Spring MVC子容器是如何体现出父子关系的

所谓容器,就是上下文,在这同一个上下文里,大家可以共享一些东西。

Spring应用启动时,会先读取web.xml文件,调用ContextLoaderListener创建Spring容器,也就是你说的父容器。

    <listener>
        <listener-class>org.springframework.web.context.ContextLoaderListener</listener-class>
    </listener>

Listener创建完之后,开始创建Servlet:

    <servlet>
        <servlet-name>SpringMVC</servlet-name>
        <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
    </servlet>

这时候这个DispatcherServlet开始试图创建SpringMVCApplicationContext,它先找刚才由上面那个ContextLoaderListener创建的SpringApplicationContext,找到后,把SpringApplicationContext作为参数传给DispatcherServletApplicationContextsetParent方法,这样SpringMVC的容器就变成了Spring容器的儿子。

因为在SpringMVC这个子容器创建的时候指定了它的Spring父容器,所以儿子能找到父亲,所以SpringMVC这个子容器里的Bean可以调用父容器的服务,而父容器不知道有这个儿子的存在(一个不负责任的父亲),父容器里的Bean不能调用子容器里的服务。

关注 5 回答 4

loserwang 提出了问题 · 10月11日

解决数据库连接url后缀太长了

在学习项目开发中,经常提示数据库报错,可能是时区错误,可能是编码错误, 查到的解决办法都是加入后缀信息。不知不觉就变成了b.url=jdbc:mysql://localhost:3306/test\_mybatis?characterEncoding=utf-8&serverTimezone=GMT%2B8&useSSL=false&nullCatalogMeansCurrent=true。
这样的后缀也太长了,迁移到服务器,这样的后缀不一定正好符合服务器的mysql数据库吧。
是要统一对数据库进行时区设置,还是就是要使用常常的后缀。

关注 2 回答 1

loserwang 收藏了文章 · 9月17日

有关 HashMap 面试会问的一切

前言

大家好,本篇文章是《齐姐说数据结构》系列的第三篇,更多数据结构和算法的文章已经整理在我的 Github 上了:https://github.com/xiaoqi6666...

HashMap 是无论在工作还是面试中都非常常见常考的数据结构。

比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的,高频考题 LRU Cache 是需要用到 LinkedHashMap 的。

HashMap 用起来很简单,底层实现也不复杂,先来看几道常见的面试题吧。相信大家多多少少都能回答上来一点,不清楚的地方就仔细阅读本文啦~这篇文章带你深挖到 HashMap 的老祖宗,保证吊打面试官

  • == 和 equals() 的区别?
  • 为什么重写 equals() 就必须要重写 hashCode()?
  • Hashtable, HashSet 和 HashMap 的区别和联系
  • 处理 hash 冲突有哪些方法?Java 中用的哪一种?为什么?另一种方法你在工作中用过吗?在什么情况下用得多?
  • 徒手实现一个 HashMap 吧

本文分以下章节:

  • Set 和 Map 家族简介
  • HashMap 实现原理
  • 哈希冲突详解
  • HashMap 基本操作
  • 习题 Two Sum
  • 习题 LRU

Set 家族

在讲 Map 之前,我们先来看看 Set。

集合的概念我们初中数学就学过了,就是里面不能有重复元素,这里也是一样。

Set 在 Java 中是一个接口,可以看到它是 java.util 包中的一个集合框架类,具体的实现类有很多:

其中比较常用的有三种:

HashSet: 采用 Hashmap 的 key 来储存元素,主要特点是无序的,基本操作都是 O(1) 的时间复杂度,很快。

LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构,特点就是既拥有了 O(1) 的时间复杂度,又能够保留插入的顺序。

TreeSet: 采用红黑树结构,特点是可以有序,可以用自然排序或者自定义比较器来排序;缺点就是查询速度没有 HashSet 快。

Map 家族

Map 是一个键值对 (Key - Value pairs),其中 key 是不可以重复的,毕竟 set 中的 key 要存在这里面。

那么与 Set 相对应的,Map 也有这三个实现类:

HashMap: 与 HashSet 对应,也是无序的,O(1)。

LinkedHashMap: 这是一个「HashMap + 双向链表」的结构,落脚点是 HashMap,所以既拥有 HashMap 的所有特性还能有顺序。

TreeMap: 是有序的,本质是用二叉搜索树来实现的。

HashMap 实现原理

对于 HashMap 中的每个 key,首先通过 hash function 计算出一个 hash 值,这个hash值就代表了在 buckets 里的编号,而 buckets 实际上是用数组来实现的,所以把这个数值模上数组的长度得到它在数组的 index,就这样把它放在了数组里。

那么这里有几个问题:

如果不同的元素算出了相同的哈希值,那么该怎么存放呢?

答:这就是哈希碰撞,即多个 key 对应了同一个桶。

HashMap 中是如何保证元素的唯一性的呢?即相同的元素会不会算出不同的哈希值呢?

答:通过 hashCode()equals() 方法来保证元素的唯一性。

如果 pairs 太多,buckets 太少怎么破?

答:Rehasing. 也就是碰撞太多的时候,会把数组扩容至两倍(默认)。所以这样虽然 hash 值没有变,但是因为数组的长度变了,所以算出来的 index 就变了,就会被分配到不同的位置上了,就不用挤在一起了,小伙伴们我们江湖再见~

那什么时候会 rehashing 呢?也就是怎么衡量桶里是不是足够拥挤要扩容了呢?

答:load factor. 即用 pair 的数量除以 buckets 的数量,也就是平均每个桶里装几对。Java 中默认值是 0.75f,如果超过了这个值就会 rehashing.

关于 hashCode() 和 equals()

如果 key 的 hashCode() 值相同,那么有可能是要发生 hash collision 了,也有可能是真的遇到了另一个自己。那么如何判断呢?继续用 equals() 来比较。

也就是说,

hashCode() 决定了 key 放在这个桶里的编号,也就是在数组里的 index;

equals() 是用来比较两个 object 是否相同的。

那么该如何回答这道<span style="color:black;font-weight:bold;">经典面试题</span>:

<span style="color:blue;font-weight:bold;">为什么重写 equals() 方法,一定要重写 hashCode() 呢?

答:首先我们有一个假设:任何两个 object 的 hashCode 都是不同的。

那么在这个条件下,有两个 object 是相等的,那如果不重写 hashCode(),算出来的哈希值都不一样,就会去到不同的 buckets 了,就迷失在茫茫人海中了,再也无法相认,就和 equals() 条件矛盾了,证毕。

撒花~~🎉🎉🎉

接下来我们再对这两个方法一探究竟:

其实 hashCode() 和 equals() 方法都是在 Object class 这个老祖宗里定义的,Object 是所有 Java 中的 class 的鼻祖,默认都是有的,甩不掉的。

那既然是白给的,我们先来看看大礼包里有什么,谷歌 Object 的 Oracle 文档:

所以这些方法都是可以直接拿来用的呢~

回到 hashCode() 和 equals(),那么如果这个新的 class 里没有重写 (override) 这两个方法,就是默认继承 Object class 里的定义了。

那我们点进去来看看 equals() 是怎么定义的:

记笔记:

equals() 方法就是比较这两个 references 是否指向了同一个 object.

嗯???你在逗我吗??那岂不是和 == 一样了??

补充:
我们常用的比较大小的符号之 ==
如果是 primitive type,那么 == 就是比较数值的大小;
如果是 reference type,那么就比较的是这两个 reference 是否指向了同一个 object。

再补充:
Java 的数据类型可以分为两种:
Primitive type 有且仅有8种:byte, short, int, long, float, double, char, boolean.
其他都是 Reference type.
所以虽然 Java 声称 “Everything is object”,但是还是有非 object 数据类型的存在的。

我不信,我要去源码里看看它是怎么实现的。

哈,还真是的,绕了这么半天,equals() 就是用 == 来实现的!

那为什么还弄出来这么个方法呢?

<span style="color:blue;font-weight:bold;">答:为了让你 override~

比如一般来说我们比较字符串就是想比较这两个字符串的内容的,那么:

str1 = “tianxiaoqi”;
str2 =  new String(“tianxiaoqi”);

str1 == str2; // return false
str1.equals(str2); // return true 

因为 String 里是重写了 equals() 方法的:

老祖宗留给你就是让你自己用的,如果你不用,那人家也提供了默认的方法,也是够意思了。

好了,我们再去看 hashCode() 的介绍:

那至于 hashCode() 返回的究竟是什么,和本文关联不太大,有兴趣的同学可以看参考这篇文章参考文章"),结论就是:

返回的并不一定是对象的(虚拟)内存地址,具体取决于运行时库和JVM的具体实现。

但无论是怎么实现的,都需要遵循文档上的约定,也就是对不同的 object 会返回唯一的哈希值

### 哈希冲突详解

一般来说哈希冲突有两大类解决方式

  1. Separate chaining
  2. Open addressing

Java 中采用的是第一种 Separate chaining,即在发生碰撞的那个桶后面再加一条“链”来存储,那么这个“链”使用的具体是什么数据结构,不同的版本稍有不同:

在 JDK1.6 和 1.7 中,是用链表存储的,这样如果碰撞很多的话,就变成了在链表上的查找,worst case 就是 O(n);

在 JDK 1.8 进行了优化,当链表长度较大时(超过 8),会采用红黑树来存储,这样大大提高了查找效率。

(话说,这个还真的喜欢考,已经在多次面试中被问过了,还有面试官问为什么是超过“8”才用红黑树🤔)

第二种方法 open addressing 也是非常重要的思想,因为在真实的分布式系统里,有很多地方会用到 hash 的思想但又不适合用 seprate chaining

这种方法是顺序查找,如果这个桶里已经被占了,那就按照“某种方式”继续找下一个没有被占的桶,直到找到第一个的。

空的

如图所示,John Smith 和 Sandra Dee 发生了哈希冲突,都被计算到 152 号桶,于是 Sandra 就去了下一个空位 - 153 号桶,当然也会对之后的 key 发生影响:Ted Baker 计算结果本应是放在 153 号的,但鉴于已经被 Sandra 占了,就只能再去下一个空位了,所以到了 154 号。

这种方式叫做 Linear probing 线性探查,就像上图所示,一个个的顺着找下一个空位。当然还有其他的方式,比如去找平方数,或者 Double hashing.

HashMap 基本操作

每种数据结构的基本操作都无外乎<span style="color:orangered;font-weight:bold;">增删改查</span>这四种,具体到 HashMap 来说,

  • 增:put(K key, V value)
  • 删:remove(Object key)
  • 改:还是用的 put(K key, V value)
  • 查:get(Object key) / containsKey(Object key)

细心的同学可能发现了,为什么有些 key 的类型是 Object,有些是 K 呢?这还不是因为 equals()...

这是因为,在 get/remove 的时候,不一定是用的同一个 object。

还记得那个 str1 和 str2 都是田小齐的例子吗?那比如我先 put(str1, value),然后用 get(str2) 的时候,也是想要到 tianxiaoqi 对应的 value 呀!不能因为我换了身衣服就不认得我了呀!所以在 get/remove 的时候并没有很限制 key 的类型,方便另一个自己相认。

其实这些 API 的操作流程大同小异,我们以最复杂的 put(K key, V value) 来讲:

  1. 首先要拿到 array 中要放的位置的 index
  • 怎么找 index 呢,这里我们可以单独用 getIndex() method 来做这件事;
  • 具体怎么做,就是通过 hash function 算出来的值,模上数组的长度;
  1. 那拿到了这个位置的 Node,我们开始 traverse 这个 LinkedList,这就是在链表上的操作了,
  • 如果找的到,就更新一下 value;
  • 如果没找到,就把它放在链表上,可以放头上,也可以放尾上,一般我喜欢放头上,因为新加入的元素用到的概率总是大一些,但并不影响时间复杂度。

代码如下:

  public V put(K key, V value) {
    int index = getIndex(key);
    Node<K, V> node = array[index];
    Node<K, V> head = node; 
    while (node != null) {
        // 原来有这个 key,仅更新值
        if (checkEquals(key, node)) {
            V preValue = node.value;
            node.value = value;
            return preValue;
        }
        node = node.next;
    }
    // 原来没有这个 key,新加这个 node
    Node<K, V> newNode = new Node(key, value); 
    newNode.next = head;
    array[index] = newNode;
    return null;
}

至于更多的细节比如加一些 rehashing 啊,load factor 啊,大家可以参考源码。

读完源码大家可以做做 Leetcode 706 题练手,so easy~

### 与 Hashtable 的区别

这是一个年龄暴露贴,HashMap 与 Hashtable 的关系,就像 ArrayList 与 Vector,以及 StringBuilder 与 StringBuffer。

Hashtable 是早期 JDK 提供的接口,HashMap 是新版的;
它们之间最显著的区别,就是 Hashtable 是线程安全的,HashMap 并非线程安全。

这是因为 Java 5.0 之后允许数据结构不考虑线程安全的问题,因为实际工作中我们发现没有必要在数据结构的层面上上锁,加锁和放锁在系统中是有开销的,内部锁有时候会成为程序的瓶颈。

所以 HashMap, ArrayList, StringBuilder 不再考虑线程安全的问题,性能提升了很多,当然,线程安全问题也就转移给我们程序员了。

另外一个区别就是:HashMap 允许 key 中有 null 值,Hashtable 是不允许的。这样的好处就是可以给一个默认值。

在算法面试中,有关 HashMap 的算法题也很常见,比如有名的 Top K 问题,还有 LRU Cache 问题,这两道题都是非常高频的考题,之后也会讲到,还请大家继续关注我吧!


如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

loserwang 赞了文章 · 9月17日

有关 HashMap 面试会问的一切

前言

大家好,本篇文章是《齐姐说数据结构》系列的第三篇,更多数据结构和算法的文章已经整理在我的 Github 上了:https://github.com/xiaoqi6666...

HashMap 是无论在工作还是面试中都非常常见常考的数据结构。

比如 Leetcode 第一题 Two Sum 的某种变种的最优解就是需要用到 HashMap 的,高频考题 LRU Cache 是需要用到 LinkedHashMap 的。

HashMap 用起来很简单,底层实现也不复杂,先来看几道常见的面试题吧。相信大家多多少少都能回答上来一点,不清楚的地方就仔细阅读本文啦~这篇文章带你深挖到 HashMap 的老祖宗,保证吊打面试官

  • == 和 equals() 的区别?
  • 为什么重写 equals() 就必须要重写 hashCode()?
  • Hashtable, HashSet 和 HashMap 的区别和联系
  • 处理 hash 冲突有哪些方法?Java 中用的哪一种?为什么?另一种方法你在工作中用过吗?在什么情况下用得多?
  • 徒手实现一个 HashMap 吧

本文分以下章节:

  • Set 和 Map 家族简介
  • HashMap 实现原理
  • 哈希冲突详解
  • HashMap 基本操作
  • 习题 Two Sum
  • 习题 LRU

Set 家族

在讲 Map 之前,我们先来看看 Set。

集合的概念我们初中数学就学过了,就是里面不能有重复元素,这里也是一样。

Set 在 Java 中是一个接口,可以看到它是 java.util 包中的一个集合框架类,具体的实现类有很多:

其中比较常用的有三种:

HashSet: 采用 Hashmap 的 key 来储存元素,主要特点是无序的,基本操作都是 O(1) 的时间复杂度,很快。

LinkedHashSet: 这个是一个 HashSet + LinkedList 的结构,特点就是既拥有了 O(1) 的时间复杂度,又能够保留插入的顺序。

TreeSet: 采用红黑树结构,特点是可以有序,可以用自然排序或者自定义比较器来排序;缺点就是查询速度没有 HashSet 快。

Map 家族

Map 是一个键值对 (Key - Value pairs),其中 key 是不可以重复的,毕竟 set 中的 key 要存在这里面。

那么与 Set 相对应的,Map 也有这三个实现类:

HashMap: 与 HashSet 对应,也是无序的,O(1)。

LinkedHashMap: 这是一个「HashMap + 双向链表」的结构,落脚点是 HashMap,所以既拥有 HashMap 的所有特性还能有顺序。

TreeMap: 是有序的,本质是用二叉搜索树来实现的。

HashMap 实现原理

对于 HashMap 中的每个 key,首先通过 hash function 计算出一个 hash 值,这个hash值就代表了在 buckets 里的编号,而 buckets 实际上是用数组来实现的,所以把这个数值模上数组的长度得到它在数组的 index,就这样把它放在了数组里。

那么这里有几个问题:

如果不同的元素算出了相同的哈希值,那么该怎么存放呢?

答:这就是哈希碰撞,即多个 key 对应了同一个桶。

HashMap 中是如何保证元素的唯一性的呢?即相同的元素会不会算出不同的哈希值呢?

答:通过 hashCode()equals() 方法来保证元素的唯一性。

如果 pairs 太多,buckets 太少怎么破?

答:Rehasing. 也就是碰撞太多的时候,会把数组扩容至两倍(默认)。所以这样虽然 hash 值没有变,但是因为数组的长度变了,所以算出来的 index 就变了,就会被分配到不同的位置上了,就不用挤在一起了,小伙伴们我们江湖再见~

那什么时候会 rehashing 呢?也就是怎么衡量桶里是不是足够拥挤要扩容了呢?

答:load factor. 即用 pair 的数量除以 buckets 的数量,也就是平均每个桶里装几对。Java 中默认值是 0.75f,如果超过了这个值就会 rehashing.

关于 hashCode() 和 equals()

如果 key 的 hashCode() 值相同,那么有可能是要发生 hash collision 了,也有可能是真的遇到了另一个自己。那么如何判断呢?继续用 equals() 来比较。

也就是说,

hashCode() 决定了 key 放在这个桶里的编号,也就是在数组里的 index;

equals() 是用来比较两个 object 是否相同的。

那么该如何回答这道<span style="color:black;font-weight:bold;">经典面试题</span>:

<span style="color:blue;font-weight:bold;">为什么重写 equals() 方法,一定要重写 hashCode() 呢?

答:首先我们有一个假设:任何两个 object 的 hashCode 都是不同的。

那么在这个条件下,有两个 object 是相等的,那如果不重写 hashCode(),算出来的哈希值都不一样,就会去到不同的 buckets 了,就迷失在茫茫人海中了,再也无法相认,就和 equals() 条件矛盾了,证毕。

撒花~~🎉🎉🎉

接下来我们再对这两个方法一探究竟:

其实 hashCode() 和 equals() 方法都是在 Object class 这个老祖宗里定义的,Object 是所有 Java 中的 class 的鼻祖,默认都是有的,甩不掉的。

那既然是白给的,我们先来看看大礼包里有什么,谷歌 Object 的 Oracle 文档:

所以这些方法都是可以直接拿来用的呢~

回到 hashCode() 和 equals(),那么如果这个新的 class 里没有重写 (override) 这两个方法,就是默认继承 Object class 里的定义了。

那我们点进去来看看 equals() 是怎么定义的:

记笔记:

equals() 方法就是比较这两个 references 是否指向了同一个 object.

嗯???你在逗我吗??那岂不是和 == 一样了??

补充:
我们常用的比较大小的符号之 ==
如果是 primitive type,那么 == 就是比较数值的大小;
如果是 reference type,那么就比较的是这两个 reference 是否指向了同一个 object。

再补充:
Java 的数据类型可以分为两种:
Primitive type 有且仅有8种:byte, short, int, long, float, double, char, boolean.
其他都是 Reference type.
所以虽然 Java 声称 “Everything is object”,但是还是有非 object 数据类型的存在的。

我不信,我要去源码里看看它是怎么实现的。

哈,还真是的,绕了这么半天,equals() 就是用 == 来实现的!

那为什么还弄出来这么个方法呢?

<span style="color:blue;font-weight:bold;">答:为了让你 override~

比如一般来说我们比较字符串就是想比较这两个字符串的内容的,那么:

str1 = “tianxiaoqi”;
str2 =  new String(“tianxiaoqi”);

str1 == str2; // return false
str1.equals(str2); // return true 

因为 String 里是重写了 equals() 方法的:

老祖宗留给你就是让你自己用的,如果你不用,那人家也提供了默认的方法,也是够意思了。

好了,我们再去看 hashCode() 的介绍:

那至于 hashCode() 返回的究竟是什么,和本文关联不太大,有兴趣的同学可以看参考这篇文章参考文章"),结论就是:

返回的并不一定是对象的(虚拟)内存地址,具体取决于运行时库和JVM的具体实现。

但无论是怎么实现的,都需要遵循文档上的约定,也就是对不同的 object 会返回唯一的哈希值

### 哈希冲突详解

一般来说哈希冲突有两大类解决方式

  1. Separate chaining
  2. Open addressing

Java 中采用的是第一种 Separate chaining,即在发生碰撞的那个桶后面再加一条“链”来存储,那么这个“链”使用的具体是什么数据结构,不同的版本稍有不同:

在 JDK1.6 和 1.7 中,是用链表存储的,这样如果碰撞很多的话,就变成了在链表上的查找,worst case 就是 O(n);

在 JDK 1.8 进行了优化,当链表长度较大时(超过 8),会采用红黑树来存储,这样大大提高了查找效率。

(话说,这个还真的喜欢考,已经在多次面试中被问过了,还有面试官问为什么是超过“8”才用红黑树🤔)

第二种方法 open addressing 也是非常重要的思想,因为在真实的分布式系统里,有很多地方会用到 hash 的思想但又不适合用 seprate chaining

这种方法是顺序查找,如果这个桶里已经被占了,那就按照“某种方式”继续找下一个没有被占的桶,直到找到第一个的。

空的

如图所示,John Smith 和 Sandra Dee 发生了哈希冲突,都被计算到 152 号桶,于是 Sandra 就去了下一个空位 - 153 号桶,当然也会对之后的 key 发生影响:Ted Baker 计算结果本应是放在 153 号的,但鉴于已经被 Sandra 占了,就只能再去下一个空位了,所以到了 154 号。

这种方式叫做 Linear probing 线性探查,就像上图所示,一个个的顺着找下一个空位。当然还有其他的方式,比如去找平方数,或者 Double hashing.

HashMap 基本操作

每种数据结构的基本操作都无外乎<span style="color:orangered;font-weight:bold;">增删改查</span>这四种,具体到 HashMap 来说,

  • 增:put(K key, V value)
  • 删:remove(Object key)
  • 改:还是用的 put(K key, V value)
  • 查:get(Object key) / containsKey(Object key)

细心的同学可能发现了,为什么有些 key 的类型是 Object,有些是 K 呢?这还不是因为 equals()...

这是因为,在 get/remove 的时候,不一定是用的同一个 object。

还记得那个 str1 和 str2 都是田小齐的例子吗?那比如我先 put(str1, value),然后用 get(str2) 的时候,也是想要到 tianxiaoqi 对应的 value 呀!不能因为我换了身衣服就不认得我了呀!所以在 get/remove 的时候并没有很限制 key 的类型,方便另一个自己相认。

其实这些 API 的操作流程大同小异,我们以最复杂的 put(K key, V value) 来讲:

  1. 首先要拿到 array 中要放的位置的 index
  • 怎么找 index 呢,这里我们可以单独用 getIndex() method 来做这件事;
  • 具体怎么做,就是通过 hash function 算出来的值,模上数组的长度;
  1. 那拿到了这个位置的 Node,我们开始 traverse 这个 LinkedList,这就是在链表上的操作了,
  • 如果找的到,就更新一下 value;
  • 如果没找到,就把它放在链表上,可以放头上,也可以放尾上,一般我喜欢放头上,因为新加入的元素用到的概率总是大一些,但并不影响时间复杂度。

代码如下:

  public V put(K key, V value) {
    int index = getIndex(key);
    Node<K, V> node = array[index];
    Node<K, V> head = node; 
    while (node != null) {
        // 原来有这个 key,仅更新值
        if (checkEquals(key, node)) {
            V preValue = node.value;
            node.value = value;
            return preValue;
        }
        node = node.next;
    }
    // 原来没有这个 key,新加这个 node
    Node<K, V> newNode = new Node(key, value); 
    newNode.next = head;
    array[index] = newNode;
    return null;
}

至于更多的细节比如加一些 rehashing 啊,load factor 啊,大家可以参考源码。

读完源码大家可以做做 Leetcode 706 题练手,so easy~

### 与 Hashtable 的区别

这是一个年龄暴露贴,HashMap 与 Hashtable 的关系,就像 ArrayList 与 Vector,以及 StringBuilder 与 StringBuffer。

Hashtable 是早期 JDK 提供的接口,HashMap 是新版的;
它们之间最显著的区别,就是 Hashtable 是线程安全的,HashMap 并非线程安全。

这是因为 Java 5.0 之后允许数据结构不考虑线程安全的问题,因为实际工作中我们发现没有必要在数据结构的层面上上锁,加锁和放锁在系统中是有开销的,内部锁有时候会成为程序的瓶颈。

所以 HashMap, ArrayList, StringBuilder 不再考虑线程安全的问题,性能提升了很多,当然,线程安全问题也就转移给我们程序员了。

另外一个区别就是:HashMap 允许 key 中有 null 值,Hashtable 是不允许的。这样的好处就是可以给一个默认值。

在算法面试中,有关 HashMap 的算法题也很常见,比如有名的 Top K 问题,还有 LRU Cache 问题,这两道题都是非常高频的考题,之后也会讲到,还请大家继续关注我吧!


如果你喜欢这篇文章,记得给我点赞留言哦~你们的支持和认可,就是我创作的最大动力,我们下篇文章见!

我是小齐,纽约程序媛,终生学习者,每天晚上 9 点,云自习室里不见不散!

更多干货文章见我的 Github: https://github.com/xiaoqi6666...

查看原文

赞 22 收藏 15 评论 0

loserwang 收藏了文章 · 9月17日

Java 程序员必备的 15 个框架,前 3 个地位无可动摇!

Java 程序员方向太多,且不说移动开发、大数据、区块链、人工智能这些,大部分 Java 程序员都是 Java Web/后端开发。那作为一名 Java Web 开发程序员必须需要熟悉哪些框架呢?

今天,栈长我给大家列举了一些通用的、必须掌握的框架,学会这些,20K+ 不是问题。

1.Spring

毫无疑问,Spring 框架现在是 Java 后端框架家族里面最强大的一个,其拥有 IOC 和 AOP 两大利器,大大简化了软件开发复杂性。并且,Spring 现在能与所有主流开发框架集成,可谓是一个万能框架,Spring 让 JAVA 开发变得更多简单。

官网:

https://spring.io/projects/sp...

源码:

https://github.com/spring-pro...

推荐:

Java 必看的 Spring 知识汇总

更多请在Java技术栈微信公众号后台回复关键字:spring。

2.Spring MVC

Spring MVC 是一个 MVC 开源框架,用来代替 Struts。它是 Spring 项目里面的一个重要组成部分,能与 Spring IOC 容器紧密结合,以及拥有松耦合、方便配置、代码分离等特点,让 JAVA 程序员开发 WEB 项目变得更加容易。

官网:

https://spring.io/projects/sp...

源码:

https://github.com/spring-pro...

推荐:

从 0 开始手写一个 Spring MVC 框架

更多请在Java技术栈微信公众号后台回复关键字:mvc。

3.Spring Boot

Spring Boot 是 Spring 开源组织下的一个子项目,也是 Spring 组件一站式解决方案,主要是为了简化使用 Spring 框架的难度,简省繁重的配置。

Spring Boot提供了各种组件的启动器(starters),开发者只要能配置好对应组件参数,Spring Boot 就会自动配置,让开发者能快速搭建依赖于 Spring 组件的 Java 项目。

官网:

https://spring.io/projects/sp...

源码:

https://github.com/spring-pro...

推荐:

更多请在Java技术栈微信公众号后台回复关键字:boot。

4.Spring Cloud

Spring Cloud 是一系列框架的有序集合,是目前最火热的微服务框架首选,它利用Spring Boot 的开发便利性巧妙地简化了分布式系统基础设施的开发,如服务发现注册、配置中心、消息总线、负载均衡、断路器、数据监控等,都可以用 Spring Boot 的开发风格做到一键启动和部署。

官网:

http://projects.spring.io/spr...

源码:

https://github.com/spring-cloud

推荐:

更多请在Java技术栈微信公众号后台回复关键字:cloud。

5.Mybatis/ iBatis

iBatis 曾是开源软件组 Apache 推出的一种轻量级的对象关系映射持久层(ORM)框架,随着开发团队转投Google Code 旗下,ibatis 3.x 正式更名为 Mybatis,即:iBatis 2.x, MyBatis 3.x。

官网:

http://www.mybatis.org/mybati...

源码:

https://github.com/mybatis

推荐:

Mybatis 传递多个参数的 4 种方式

更多请关注Java技术栈微信公众号,在后台回复:mybatis。

6.Hibernate

Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,它将 POJO 与数据库表建立映射关系,是一个全自动的 orm 框架。Hibernate 可以自动生成 SQL 语句,自动执行,使得 Java 程序员可以随心所欲的使用对象编程思维来操作数据库。

官网:

http://hibernate.org/

源码:

https://github.com/hibernate

7.Dubbo

Dubbo是阿里巴巴开源的基于 Java 的高性能 RPC 分布式服务框架,现已成为 Apache 基金会孵化项目。使用 Dubbo 可以将核心业务抽取出来,作为独立的服务,逐渐形成稳定的服务中心,可用于提高业务复用灵活扩展,使前端应用能更快速的响应多变的市场需求。

官网:

http://dubbo.apache.org

源码:

https://github.com/apache/inc...

推荐:

更多请在Java技术栈微信公众号后台回复关键字:dubbo。

8.Netty

Netty 是由 JBOSS 提供的一个开源的、异步的、基于事件驱动的网络通信框架,用 Netty 可以快速开发高性能、高可靠性的网络服务器和客户端程序,Netty 简化了网络应用的编程开发过程,使开发网络编程变得异常简单。

官网:

https://netty.io/

源码:

https://github.com/netty/netty

9.Shiro

Apache Shiro是一个强大而灵活的开源安全框架,它干净利落地处理身份认证,授权,企业会话管理和加密。

官网:

http://shiro.apache.org/

源码:

https://github.com/apache/shiro

10.Ehcache

EhCache 是一个纯Java的进程内缓存框架,具有快速、精干等特点,是 Hibernate 中默认的CacheProvider。它使用的是 JVM 的堆内存,超过内存可以设置缓存到磁盘,企业版的可以使用 JVM 堆外的物理内存。

官网:

http://www.ehcache.org/

源码:

https://github.com/ehcache/eh...

推荐:

Ehcache介绍及整合Spring实现高速缓存

更多请在Java技术栈微信公众号后台回复关键字:ehcache。

11.Quartz

Quartz 是一个基于 Java 的广泛使用的开源的任务调度框架,做过定时任务的没有没用过这个框架的吧?

官网:

http://www.quartz-scheduler.org/

源码:

https://github.com/quartz-sch...

12.Velocity

Velocity 是一个基于 Java 的模板引擎,简单而强大的模板语言为各种 Web 框架提供模板服务,来适配 MVC 模型。

官网:

http://velocity.apache.org/

源码:

https://github.com/apache/vel...

13.jQuery

jQuery是一个快速、简洁的 JavaScript 框架,它封装 JavaScript 常用的功能代码,提供一种简便的 JavaScript 设计模式,极大地简化了 JavaScript 编程。

虽然哥好久没做 Web 开发了,但哥也不曾忘记,也还记得一些常用的写法,如:

$("#wx").html("javastack");

官网:

http://jquery.com/

源码:

http://jquery.com/download/

14.JUnit

JUnit 是一个 Java 语言的单元测试框架,绝大多数 Java 的开发环境都已经集成了 JUnit 作为其单元测试的工具。

官网:

https://junit.org

源码:

https://github.com/junit-team/

15.Log4j

Log4j 是 Apache 的一个开源日志框架,通过 Log4j 我们可以将程序中的日志信息输出到控制台、文件等来记录日志。作为一个最老牌的日志框架,它现在的主流版本是 Log4j2。Log4j2是重新架构的一款日志框架,抛弃了之前 Log4j 的不足,以及吸取了优秀日志框架 Logback 的设计。

官网:

https://logging.apache.org/lo...

源码:

https://logging.apache.org/lo...

如果上面的大部分没用过,甚至都没听说过,那就怀疑你是不是个假程序员了,要加油了。

这些都是 Java 程序员必备的开发框架,有些不一定是首选的选择,但这些一定是 Java 程序员必备的。。

本文原创首发于微信公众号:Java技术栈(id:javastack),关注公众号在后台回复 "java" 可获取更多,转载请原样保留本信息。

查看原文

loserwang 赞了文章 · 9月17日

Java 程序员必备的 15 个框架,前 3 个地位无可动摇!

Java 程序员方向太多,且不说移动开发、大数据、区块链、人工智能这些,大部分 Java 程序员都是 Java Web/后端开发。那作为一名 Java Web 开发程序员必须需要熟悉哪些框架呢?

今天,栈长我给大家列举了一些通用的、必须掌握的框架,学会这些,20K+ 不是问题。

1.Spring

毫无疑问,Spring 框架现在是 Java 后端框架家族里面最强大的一个,其拥有 IOC 和 AOP 两大利器,大大简化了软件开发复杂性。并且,Spring 现在能与所有主流开发框架集成,可谓是一个万能框架,Spring 让 JAVA 开发变得更多简单。

官网:

https://spring.io/projects/sp...

源码:

https://github.com/spring-pro...

推荐:

Java 必看的 Spring 知识汇总

更多请在Java技术栈微信公众号后台回复关键字:spring。

2.Spring MVC

Spring MVC 是一个 MVC 开源框架,用来代替 Struts。它是 Spring 项目里面的一个重要组成部分,能与 Spring IOC 容器紧密结合,以及拥有松耦合、方便配置、代码分离等特点,让 JAVA 程序员开发 WEB 项目变得更加容易。

官网:

https://spring.io/projects/sp...

源码:

https://github.com/spring-pro...

推荐:

从 0 开始手写一个 Spring MVC 框架

更多请在Java技术栈微信公众号后台回复关键字:mvc。

3.Spring Boot

Spring Boot 是 Spring 开源组织下的一个子项目,也是 Spring 组件一站式解决方案,主要是为了简化使用 Spring 框架的难度,简省繁重的配置。

Spring Boot提供了各种组件的启动器(starters),开发者只要能配置好对应组件参数,Spring Boot 就会自动配置,让开发者能快速搭建依赖于 Spring 组件的 Java 项目。

官网:

https://spring.io/projects/sp...

源码:

https://github.com/spring-pro...

推荐:

更多请在Java技术栈微信公众号后台回复关键字:boot。

4.Spring Cloud

Spring Cloud 是一系列框架的有序集合,是目前最火热的微服务框架首选,它利用Spring Boot 的开发便利性巧妙地简化了分布式系统基础设施的开发,如服务发现注册、配置中心、消息总线、负载均衡、断路器、数据监控等,都可以用 Spring Boot 的开发风格做到一键启动和部署。

官网:

http://projects.spring.io/spr...

源码:

https://github.com/spring-cloud

推荐:

更多请在Java技术栈微信公众号后台回复关键字:cloud。

5.Mybatis/ iBatis

iBatis 曾是开源软件组 Apache 推出的一种轻量级的对象关系映射持久层(ORM)框架,随着开发团队转投Google Code 旗下,ibatis 3.x 正式更名为 Mybatis,即:iBatis 2.x, MyBatis 3.x。

官网:

http://www.mybatis.org/mybati...

源码:

https://github.com/mybatis

推荐:

Mybatis 传递多个参数的 4 种方式

更多请关注Java技术栈微信公众号,在后台回复:mybatis。

6.Hibernate

Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,它将 POJO 与数据库表建立映射关系,是一个全自动的 orm 框架。Hibernate 可以自动生成 SQL 语句,自动执行,使得 Java 程序员可以随心所欲的使用对象编程思维来操作数据库。

官网:

http://hibernate.org/

源码:

https://github.com/hibernate

7.Dubbo

Dubbo是阿里巴巴开源的基于 Java 的高性能 RPC 分布式服务框架,现已成为 Apache 基金会孵化项目。使用 Dubbo 可以将核心业务抽取出来,作为独立的服务,逐渐形成稳定的服务中心,可用于提高业务复用灵活扩展,使前端应用能更快速的响应多变的市场需求。

官网:

http://dubbo.apache.org

源码:

https://github.com/apache/inc...

推荐:

更多请在Java技术栈微信公众号后台回复关键字:dubbo。

8.Netty

Netty 是由 JBOSS 提供的一个开源的、异步的、基于事件驱动的网络通信框架,用 Netty 可以快速开发高性能、高可靠性的网络服务器和客户端程序,Netty 简化了网络应用的编程开发过程,使开发网络编程变得异常简单。

官网:

https://netty.io/

源码:

https://github.com/netty/netty

9.Shiro

Apache Shiro是一个强大而灵活的开源安全框架,它干净利落地处理身份认证,授权,企业会话管理和加密。

官网:

http://shiro.apache.org/

源码:

https://github.com/apache/shiro

10.Ehcache

EhCache 是一个纯Java的进程内缓存框架,具有快速、精干等特点,是 Hibernate 中默认的CacheProvider。它使用的是 JVM 的堆内存,超过内存可以设置缓存到磁盘,企业版的可以使用 JVM 堆外的物理内存。

官网:

http://www.ehcache.org/

源码:

https://github.com/ehcache/eh...

推荐:

Ehcache介绍及整合Spring实现高速缓存

更多请在Java技术栈微信公众号后台回复关键字:ehcache。

11.Quartz

Quartz 是一个基于 Java 的广泛使用的开源的任务调度框架,做过定时任务的没有没用过这个框架的吧?

官网:

http://www.quartz-scheduler.org/

源码:

https://github.com/quartz-sch...

12.Velocity

Velocity 是一个基于 Java 的模板引擎,简单而强大的模板语言为各种 Web 框架提供模板服务,来适配 MVC 模型。

官网:

http://velocity.apache.org/

源码:

https://github.com/apache/vel...

13.jQuery

jQuery是一个快速、简洁的 JavaScript 框架,它封装 JavaScript 常用的功能代码,提供一种简便的 JavaScript 设计模式,极大地简化了 JavaScript 编程。

虽然哥好久没做 Web 开发了,但哥也不曾忘记,也还记得一些常用的写法,如:

$("#wx").html("javastack");

官网:

http://jquery.com/

源码:

http://jquery.com/download/

14.JUnit

JUnit 是一个 Java 语言的单元测试框架,绝大多数 Java 的开发环境都已经集成了 JUnit 作为其单元测试的工具。

官网:

https://junit.org

源码:

https://github.com/junit-team/

15.Log4j

Log4j 是 Apache 的一个开源日志框架,通过 Log4j 我们可以将程序中的日志信息输出到控制台、文件等来记录日志。作为一个最老牌的日志框架,它现在的主流版本是 Log4j2。Log4j2是重新架构的一款日志框架,抛弃了之前 Log4j 的不足,以及吸取了优秀日志框架 Logback 的设计。

官网:

https://logging.apache.org/lo...

源码:

https://logging.apache.org/lo...

如果上面的大部分没用过,甚至都没听说过,那就怀疑你是不是个假程序员了,要加油了。

这些都是 Java 程序员必备的开发框架,有些不一定是首选的选择,但这些一定是 Java 程序员必备的。。

本文原创首发于微信公众号:Java技术栈(id:javastack),关注公众号在后台回复 "java" 可获取更多,转载请原样保留本信息。

查看原文

赞 37 收藏 29 评论 1

认证与成就

  • 获得 0 次点赞
  • 获得 3 枚徽章 获得 0 枚金徽章, 获得 0 枚银徽章, 获得 3 枚铜徽章

擅长技能
编辑

(゚∀゚ )
暂时没有

开源项目 & 著作
编辑

(゚∀゚ )
暂时没有

注册于 7月24日
个人主页被 136 人浏览