备战实习记录之【字符串篇】+【哈希表篇】

三、字符串篇

1.字符串是若干字符组成的有限序列，也可以理解为是一个字符数组

2.关于库函数使用

「如果题目关键的部分直接用库函数就可以解决，建议不要使用库函数。」

「如果库函数仅仅是 解题过程中的一小部分，并且你已经很清楚这个库函数的内部实现原理的话，可以考虑使用库函数。」

3.字符串大小扩容

「其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。」

4.「当需要固定规律一段一段去处理字符串的时候，要想想在在for循环的表达式上做做文章」

5.反转字符串还有一个牛逼的用处，就是达到左旋的效果。

在Leecode151题中。「先局部反转再整体反转」达到了左旋的效果。

6.KMP

KMP的主要思想是「当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。」

KMP的精髓所在就是前缀表

使用KMP可以解决两类经典问题：

1. 匹配问题：

2. 重复子串问题

四、哈希表篇

1.哈希表

哈希表是根据关键码的值而直接进行访问的数据结构。

「一般哈希表都是用来快速判断一个元素是否出现集合里。」

2.哈希函数

哈希函数(hashFunction(字段))，通过hashCode把元素转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把元素映射为哈希表上的索引数字了。

hashCode得到的数值大于 哈希表的大小时，为了保证映射出来的索引数值都落在哈希表上，

再次对数值做一个取模的操作，就要我们就保证了元素一定可以映射到哈希表上了。

如果元素数量大于哈希表的大小，将会出现有几个不同的元素被同时映射到哈希表 同一个索引下表的位置。

即出现了「哈希碰撞」

3.哈希碰撞

方案一 拉链法：

拉链法就是要选择适当的哈希表的大小，这样既不会因为数组空值而浪费大量内存，也不会因为链表太长而在查找上浪费太多时间。

方案二 线性探测法：

使用线性探测法，一定要保证tableSize大于dataSize。我们需要依靠哈希表中的空位来解决碰撞问题。

冲突的位置，放了元素A，那么就向下找一个空位放置元素B的信息。所以要求tableSize一定要大于dataSize ，要不然哈希表上就没有空置的位置来存放 冲突的数据了。

4.哈希结构

4.1HashMap

HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null建和null值

因为key不允许重复，因此只能有一个键为null,另外HashMap不能保证放入元素的顺序，它是无序的。

HashMap是线程不安全的。

[HashMap源码]

HashMap采用hash算法来决定Map中key的存储，并通过hash算法来增加集合的大小。

hash表里可以存储元素的位置称为桶（bucket），如果通过key计算hash值发生冲突时，那么将采用链表的形式，来存储元素。

在JDK1.6，JDK1.7中，HashMap采用位桶+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。

但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。

而JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值8时，将链表转换为红黑树，这样大大减少了查找时间。
原文链接：https://blog.csdn.net/tuke_tuke/article/details/51588156

HashMap的扩容操作是一项很耗时的任务，所以如果能估算Map的容量，最好给它一个默认初始值，避免进行多次扩容。

HashMap的线程是不安全的，多线程环境中推荐是ConcurrentHashMap。

①实现原理

HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。

当我们给put(key, value)方法传递键和值时，它先调用key.hashCode()方法，返回的hashCode值，用于找到bucket位置，来储存Entry对象。

Map提供了一些常用方法，如keySet()、entrySet()等方法。

keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是返回一个Set集合，此集合的类型为Map.Entry。

“如果两个key的hashcode相同，你如何获取值对象？”答案：当我们调用get(key)方法，HashMap会使用key的hashcode值，找到bucket位置，然后获取值对象。

“如果有两个值对象，储存在同一个bucket ？”答案：将会遍历链表直到找到值对象。

“因为你并没有值对象去比较，你是如何确定确定找到值对象的？”答案：找到bucket位置之后，会调用keys.equals()方法，去找到链表中正确的节点，最终找到要找的值对象。

②底层的数据结构

　　HashMap的底层主要是基于数组和链表来实现的，它之所以有相当快的查询速度主要是因为它是通过计算散列码来决定存储的位置。

HashMap中主要是通过key的hashCode来计算hash值的，只要hashCode相同，计算出来的hash值就一样。

如果存储的对象对多了，就有可能不同的对象所算出来的hash值是相同的，这就出现了所谓的hash冲突。

学过数据结构的同学都知道，解决hash冲突的方法有很多，HashMap底层是通过链表来解决hash冲突的。

③补充知识：

HashMap是基于哈希表的 Map 接口的实现。

此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）

此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

值得注意的是HashMap不是线程安全的，如果想要线程安全的HashMap，可以通过Collections类的静态方法synchronizedMap获得线程安全的HashMap。

Map map = Collections.synchronizedMap(new HashMap());

HashMap结合了ArrayList与LinkedList两个实现的优点，虽然HashMap并不会向List的两种实现那样，在某项操作上性能较高，但是在基本操作（get 和 put）上具有稳定的性能。

5.重要tips

5.1 「一般来说哈希表都是用来快速判断一个元素是否出现集合里」。

5.2 哈希函数与哈希碰撞

哈希函数是把传入的key映射到符号表的索引上。

哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。

5.3 「虽然map是万能的，但也要知道什么时候用数组，什么时候用set」。