常见数据结构与算法问题总结

刷了挺久的leetcode了，但是对一些底层的数据结构问题还是没有仔细学习过，针对一些常见的面试问题准备一下。数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

数据的逻辑结构包括4种：

(1)集合：数据元素之间除了有相同的数据类型再没有其他的关系

(2)线性结构：数据元素之间是一对一的关系 ——线性表、栈、队列

(3)树形结构：数据元素之间是一对多的关系

(4)图状结构：数据元素之间是多对多的关系。

数组和链表

顺序存储和链式存储的区别？

顺序存储结构是用一段连续的存储空间来存储数据元素，可以进行随机访问，访问效率较高。链式存储结构是用任意的存储空间来存储数据元素，不可以进行随机访问，访问效率较低。

数组和链表的优缺点

数组的优点：使用方便，查询效率比链表高，内存是一段连续的区域

数组的缺点：大小固定，不适合动态的插入、删除，插入删除会导致大量的元素移动

链表优点：大小可变，动态添加删除效率高

缺点：只能通过顺序指针访问，查询访问效率低

从逻辑结构来看：数组的存储长度是固定的，它不能适应数据动态增减的情况。链表能够动态分配存储空间以适应数据动态增减的情况，并且易于进行插入和删除操作。

从访问方式来看：数组在内存中是一片连续的存储空间，可以通过数组下标对数组进行随机访问，访问效率较高。链表是链式存储结构，存储空间不是必须连续的，可以是任意的，访问必须从前往后依次进行，访问效率较数组来说比较低。

如果从第i个位置插入多个元素，对于数组来说每一次插入都需要往后移动元素，每一次的时间复杂度都是O(n)，而单链表来说只需要在第一次寻找i的位置时时间复杂度为O(n)，其余的插入和删除操作时间复杂度均为O(1)，提高了插入和删除的效率。

Hash表

哈希表（又叫散列表）是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希方法思想：
首先在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得 p = H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元，以后查找关键字为k的元素时，再利用哈希函数计算该元素的存储位置。再按关键字存取元素。Hash中存储的key值都是唯一的。

哈希函数的构造方法

构造哈希函数原则：
（1）函数本身便于计算
（2）计算出来的地址分布均匀，即对应任意一个关键字k，H(k)对应的不同地址的概率应该相同，以尽可能减少冲突

在实际应用中，构造哈希函数要考虑以下五个因素：
（1）计算哈希函数所需要的时间。哈希函数一定要简单，取放key值都需要根据哈希函数和key值计算位置，计算是要花时间的，尽可能要计算简单一点，这样计算时间也会少。
（2）关键字的长度。关键字过长，我们可以考虑取关键的某几位来建立哈希函数。
（3）哈希表的大小。哈希表可以减少查找次数，但是哈希表过短，或者过长都会使哈希法性能降低。
（4）关键字分布情况。为了使key值和哈希函数计算出来的地址分布均匀，要考虑关键字分布情况建立合适哈希函数。
（5）记录查找的频率。

哈希函数的构造方法包括：直接定址法，除留余数法，数字分析法，平方取中法，折叠法，随机数法：

(1)直接定址法：取关键字的某个线性函数值作为散列地址，H(key)=a*key+b。

(2)除留余数法：顾名思义，即对key值进行取余。看有多少key值，如果有几十个key值，我们可以选择对10取余，对15取余，等等。余数就是对应的地址码。

(3)数字分析法：当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列的地址，适用于所有关键字都已知的情况。

(4)平方取中法：对关键字求平方，再取结果中的中间几位作为散列地址。

(5)折叠法：将关键字分为位数相同的几部分，然后取这几部分的叠加和作为散列地址。适用于关键字位数较多，且关键字中每一位上数字分布大致均匀。

(6)随机数法：选择一个随机函数，把关键字的随机函数值作为散列地址。适合于关键字的长度不相同时。
不论什么方法，目的都是为了在保证哈希函数尽可能简单的情况下让key值计算出来的地址码尽可能均匀。即让哈希表起到提高查找效率的作用。

什么是Hash冲突（也叫“碰撞”）

当关键字集合很大的时候，关键字值不同的元素可能会映射到哈希表的同一个地址，即k1 != k2，H(k1) == H(k2)，这种现象称为冲突，此时k1和k2为同义词。事实上冲突是不可避免的，由于关键字可能发生冲突的集合远远大于实际开辟的哈希表长度 ，构成冲突的必然性，可通过改进哈希的性能来减少冲突，即降低冲突的可能性。

哈希表冲突的解决办法

1. 开放地址法：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。就是说当发生冲突时，就去寻找下一个空的地址把数据存入其中，只要哈希表足够大，就总能找到
2. 再哈希法：多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数
   计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
3. 建立公共溢出区：在创建哈希表的同时，再额外创建一个公共溢出区，专门用来存放发生哈希冲突的元素。查找时，先从哈希表查，查不到再去公共溢出区查。
4. 链地址法：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。键值对k2, v2与键值对k1, v1通过计算后的索引值都为2，这时及产生冲突，但是可以通道next指针将k2, k1所在的节点连接起来，这样就解决了哈希的冲突问题。

链地址法的优点和缺点：

优点：

1. 处理简单，无堆积现象，非同义词不会发生冲突，因此平均查找长度较短
2. 由于节点是动态申请的，因此更适合确定表前无法确定表长的情况
3. 开发地址法节点规模较大时会浪费较多空间，链地址法装填因子α较大，并且节点较大时链地址法增加的指针域可以忽略不计，因此节省空间。
4. 链地址法构造的哈希表删除节点的操作易于实现，而开放地址法构造的哈希表删除时不能直接清空被删除的节点，只能标记删除，否则将截断在该节点之后插入的同义词节点的查找路径。

缺点：

指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。

Java中HashMap和HashTable的区别

1. HashMap是Hashtable的轻量级实现（非线程安全的实现），HashMap允许空（null）键值（key）,由于非线程安全，在只有一个线程访问的情况下，效率要高于Hashtable
2. HashMap把HashTable的contains方法去掉了，改成containsValue和containsKey
3. HashTable继承自Dictionary类，而HashMap是Java1.2引进的Map interface的一个实现
4. HashMap：在不指定容量的情况下的默认容量为16;要求一定为2的整数次幂;扩容时，将容量变为原来的2倍。HashTable中hash数组默认大小是11，增加的方式是old*2+1
5. HashTable直接使用对象的hashCode，HashMap重新计算hash值