常见数据结构区别

栈和队列的区别

• 队列先进先出，栈先进后出
• 对插入和删除操作的限定不同，栈是限定只能在表的同一端进行插入和删除的线性表，队列是限定只在表的一端进行插入而另一端进行删除操作的线性表
• 遍历速度不同，栈只能从头部取数，需要遍历整个栈，而且遍历的时候需要开辟新的临时空间，队列可以从头或者尾部开始遍历，无需开辟新的临时空间，遍历过程中不影响数据结构，速度要快很多

数组和链表的区别

• 数组静态分配内存，链表动态分配内存
• 数组需要连续的内存空间，链表不需要
• 数组元素存在栈区，链表元素在堆区
• 数组查询时间为O(1)，插入为O(n),链表正好相反

HashMap和Hashtable的区别

• 继承的父类不同：Hashtable继承自Dictionary类，而HashMap继承自抽象Map类。但二者都实现了Map接口
• 线程安全性不同：Hashtable线程安全，而HashMap线程不安全。
  具体分析：Hashtable线程安全是因为每个方法中都加入了Synchronize。HashMap底层是个数组，当发生hash冲突的时候，hashmap采用链表的方式解决，在对应的数组位置存放链表的头节点。对链表而言，新加入的节点会从头节点加入。另外，resize这个操作会产生一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。
  当多个线程同时检测到总数量超过门限值得时候就会同时调用resize操作，各自生成新的数组并rehash之后赋给该map底层的数组table，结果只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题
• 是否提供contains方法：HashMap把contains方法去掉了，改成了contains Value和containsKey；而hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同
• Hash值不同：hash值得使用不同，hashtable直接使用对象的hashCode，而hashmap重新计算hash值
• 内部实现使用的数组初始化和扩容方式不同：Hashtable在不指定容量的情况下默认容量为11，而HashMap为16；Hashtable不要求底层的底层数组的数量一定为2的整数次幂，而HashMap则要求一定为2的整数次幂；Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍