5.24

1.java左移右移操作
例：计算一个32位整数的二进制形式中1的个数。
关键点：if ((n & (1<<i)) > 0)
说明：将n和1左移i位以后作与操作，得到处了第i+1为0或1，其他全为0的二进制数，即知道了数字n的二进制表示中第i+1位上是0还是1。

2.常见排序算法的主要思想以及稳定性
排序算法的稳定性：针对某个属性，属性值相同的若干个元素在排序后，针对另一属性能保持原来的排序。或者说值相等的两元素，整体排序完毕后的前后关系和排序前的是一样的。
例：两个商品的销量A>B,之前是按照商品的销量排序的，现在要求按照商品的价格排序，并且价格相同的商品保持原来的按销量排序的顺序。这时A=B，排序后AB的顺序任然是原来的顺序。
从常见排序算法的思想体会其稳定性：
（1）冒泡排序：
冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。
（2）选择排序
选择排序相当于是一种另类的冒泡排序，从第一个元素（或最后一个元素）开始，逐个和后面的每一个元素比较，若遍历到的元素比当前元素小（或大），则交换两者位置，直到遍历到结尾，则“冒”出第一个（或最后一个）气泡，然后从第二个（或倒数第二个）开始继续上面的操作，直到所有的气泡都冒出，则排序结束。由这种思想可以想到，若要求结果从小到大排序时，若当前遍历的元素和在它后面的一个元素的值相等，但是在他后面的这个与它相等的元素后面有一个比它们值小的元素，这时，遍历到这个元素就会交换位置，结果造成两个值相等的元素的位置改变了。
(3)插入排序
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素，就是第一个元素。比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。
如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
（4）快速排序
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j，交换a[i]和a[j],重复上面的过程，直到i > j。交换a[j]和a[center_index]，完成一趟快速排序。
在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j] 交换的时刻。
（5）归并排序
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素（认为直接有序）或者2个序列（1次比较和交换），然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。
那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
（6）希尔排序
不稳定的，思想后面理解

3.集合和数组的区别
1.长度上的区别：集合的长度是可变的，而数组的长度是不可变；

2.内容上的区别：数组可以是基本数据类型的数据，也可以是引用数据类型的数据；而集合只能是引用数据类型数据；

3.元素内容上的区别：数组只能存储同一种数据类型；而集合可以存储不同数据类型（其实集合一般情况下也是存储同一种数据类型）；

4.Java集合常见的接口和实现类
java常见的集合有List、Set以及Map，但是List和Set都是继承了Collection接口，而Map接口是单独的一个接口，和Collection接口属于同一级别的；

Collection接口集合：

1.List接口：元素按照进入先后有序保存，可以存储重复元素，集合中每个元素都有其对应的顺序索引；包含ArrayList、LinkedList和Vector三种接口实现类：

ArrayList：每一个ArrayList都有一个初始容量（10），该容量代表了数组的大小。随着容器中的元素不断增加，容器的大小也会随着增加。在每次向容器中增加元素的同时都会进行容量检查，当快溢出时，就会进行扩容操作。所以如果我们明确所插入元素的多少，最好指定一个初始容量值，避免过多的进行扩容操作而浪费时间、效率。
优点：底层数据结构是数组，查询快（因为地址连续，一旦数据存储好了，查询操作效率会比较高），增删慢；
缺点：非同步，线程不安全，效率高；

LinkedList：它是List接口的另一个实现，除了可以根据索引访问集合元素外，LinkedList还实现了Deque接口，可以当作双端队列来使用，也就是说，既可以当作“栈”使用，又可以当作队列使用。
优点：底层数据结构是链表，查询慢（因为LinkedList要移动指针,所以查询操作性能比较低），增删快（地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址，新增和删除操作add和remove比较快）；
缺点：非同步，线程不安全，效率高；

Vector：它与ArrayList相似，但是Vector是同步的。所以说Vector是线程安全的动态数组。
优点：底层数据结构是数组，查询快，增删慢；
缺点：同步，线程安全，效率低；

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈

Map接口集合：Map接口采用键值对Map<K,V>的存储方式，保存具有映射关系的数据，因此，Map集合里保存两组值，一组值用于保存Map里的key，另外一组值用于保存Map里的value，key和value可以是任意引用类型的数据。key值不允许重复，可以为null，所以通过指定的key就可以取出对应的value。主要实现类有：HashMap、HashTable、TreeMap、LinkedHashMap以及IdentityHashMap和WeakHashMap等；
Map 没有继承 Collection 接口，一个 Map 中不能包含相同的 key ，每个 key 只能映射一个 value

1.HashMap和HashTable
图片说明
这两者的区别主要在于以下几个方面：

不同点：
（1）父类不同：HashMap继承了AbstractMap，HashTable继承Dictionary抽象类，两者均实现Map接口；

（2）Hashtable不允许null值（包括键或值），HashMap允许一个空键（其他的空键会覆盖第一个空键）和任意数量的空值；

（3）Hashtable的方法是同步的，HashMap的方法不是同步的。这是两者最主要的区别；所以就意味着Hashtable是线程安全的，Hashtable效率较低；HashMap不是线程安全的，HashMap效率较高；
如果对同步性或与遗留代码的兼容性没有任何要求，建议使用HashMap。查看Hashtable的源代码就可以发现，除构造函数外，Hashtable的所有 public 方法声明中都有 synchronized关键字，而HashMap的源码中则没有。

（4）HashMap去掉了HashTable的contains方法，但是加上了containsValue()和containsKey()方法；
相同点：
（1）为了成功的在HashMap和Hashtable中存储和获取对象，用作key的对象必须实现hashCode()方法和equals()方法；
（2）HashMap和HashTable的数据元素是无序的；
（3）HashMap和Hashtable的底层实现都是数组+链表结构实现；

HashMap工作原理如下： HashMap基于hashing原理，通过put()和get()方法存储和获取对象。当我们将键值对传递给put()方法时，它调用建对象的hashCode()方法来计算hashCode值，然后找到bucket位置来储存值对象。当获取对象时，通过建对象的equals()方法找到正确的键值对，然后返回对象。HashMap使用链表来解决碰撞问题，当发生碰撞了，对象将会存储在链表的下一个节点中。

2.TreeMap集合：有序非线程安全基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态；
图片说明
TreeMap是SortedMap的实现类，是一个红黑树的数据结构，每个key-value对作为红黑树的一个节点。TreeMap存储key-value对时，需要根据key对节点进行排序。

TreeMap也有两种排序方式：
♦ 自然排序：TreeMap的所有key必须实现Comparable接口，而且所有的key应该是同一个类的对象，否则会抛出ClassCastException；
♦ 定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeMap中的所有key进行排序；

3.LinkedHashMap集合：
LinkedHashMap使用双向链表来维护key-value对的次序（其实只需要考虑key的次序即可），该链表负责维护Map的迭代顺序，与插入顺序一致，因此性能比HashMap低，但在迭代访问Map里的全部元素时有较好的性能。