1。 散列函数
对于字符串的散列函数，可以使用下列方式：
int hash = 0;
for(int i=0;i<s.length();i++){
hash = g * hash + s.charAt(i);//g最好是素数，比如31
}
对于字符串，如果有s1.equals(s2)，那么必有s1.hashCode() == s2.hashCode().反则不成立。
2。 如何处理哈希冲突
键值对作为在Map集合类中的存储方式，可以在值中使用一中结构，在该就够中，保存了键值，这样在不同的键有相同的hashCode时，可以根据比较值中的键来找到。
(1)线性探测开放定址。即在键冲突时，依次在后面的空间中逐次寻找探测。需要区分的散列表中的三种位置：
- 被占用 --
- 空闲 -- 该位置为null，且历来如此
- 可用 -- 该位置为null，但其中的内容是被删除之后的结果，被使用过至少一次。
为什么要区分不同的null呢？？ 有一种情况，即线性探测开放定址方法，将有相同hashCode的连续4个键放入了哈希表中，但是之后的某种情况下，删除了这4个中的第3个，而下次要想找到第4个键值对，就必须先找到第一个，然后一次查找。到达第三个时是可用状态而不是空闲状态，这样会继续寻找（如果是空闲状态的话，即不区分空闲和可以状态，则永远不会找到第四个键值对），直到找到第四个位置（如果还找不到，则遇到第五个位置时是空闲，则返回false，该哈希表中不存在该键）
(2)二次探测开放定址
探测的位置为k+j * j
(3)双散列开放定址
使用两个散列函数，如果第一个散列函数遇到冲突，则使用第二个散列函数。
(4)链地址
将相同散列值的键通过链表连接到链表的后面。该方法可以实现，按照一定的顺序进行插入。
上面四种解决冲突的方法中，链地址是比较合适的。
3。 栈
栈是一种非常常用的数据结构。在用到栈的典型问题有：判断一个数序表达式的括号是否匹配，将一个中缀表达式转变成一个后缀表达式（因为后缀表达式更容易让计算机计算），中缀表达式求值。下面将一一列出这三种情况下的程序代码。
4。 队列、双端队列、优先队列
package com.java.stack;
import java.util.Stack;
public class MyStack {
public static boolean checkBalance(String expression){
boolean balanced = true;
Stack<Character> stack = new Stack<Character>();
for(int i=0;balanced && i<expression.length();i++){
char ch = expression.charAt(i);
switch(ch){
case '(': case '[': case '{':
stack.push(ch);
break;
case ')': case ']': case '}':
if(stack.isEmpty()){
balanced = false;
}else{
char pop = stack.pop();
balanced = isPaired(pop,ch);
}
break;
}
}
if(!stack.isEmpty()){
balanced = false;
}
return balanced;
}
private static boolean isPaired(char left, char right){
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}
/**
* 这里只考虑了在 0-9的整数
* 需要处理的数据类型包括：
* 运算数 ^ + - * / ( )
* 中缀表达式转变为后缀表达式时，遇到相应的符号所对应的动作：
* 运算数： 添加到输出表达式的末尾
* ^： 压入栈
* +-* /： 从栈中弹出运算符并添加到表达式的末尾，直到栈为空或者栈顶优先级比该新的运算符低。然后将新的运算符压入栈
* ( ： 压入栈
* ) ： 从栈中弹出运算符并添加到表达式的末尾，知道弹出(，丢弃这两个括号
* @param expression
* @return
*/
public static String convert2Postfix(String expression){
Stack<Character> stack = new Stack<Character>();
StringBuffer sb = new StringBuffer();
char[] arr = expression.toCharArray();
for(int i=0;i<arr.length;i++){
char ch = arr[i];
if(isDigit(ch)){
sb.append(ch);
}else{
switch(ch){
case '^':
stack.push(ch);
break;
case '+': case '-': case '*': case '/':
while(!stack.isEmpty()){
char top = stack.peek();
if(getPrecedence(ch) <= getPrecedence(top)){
sb.append(top);
stack.pop();
}else{
break;
}
}
stack.push(ch);
break;
case '(':
stack.push(ch);
break;
case ')':
char pop = stack.pop();
while(pop != '('){
sb.append(pop);
pop = stack.pop();
}
break;
}
}
}
while(!stack.isEmpty()){
char pop = stack.pop();
sb.append(pop);
}
return sb.toString();
}
private static boolean isDigit(char ch){
return Character.isDigit(ch);
}
private static int getPrecedence(char ch){
switch(ch){
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
default: return -1;
}
}
/**
* 这里只考虑了 0-9的整数
* @param expression
* @return
*/
public static int calculatePostfixExpression(String expression){
Stack<Integer> stack = new Stack<Integer>();
char[] arr = expression.toCharArray();
for(int i=0;i<arr.length;i++){
char ch = arr[i];
if(isDigit(ch)){
stack.push(Integer.parseInt(String.valueOf(ch)));
}else{
int two = stack.pop();
int one = stack.pop();
int value = calculate(one,two,ch);
stack.push(value);
}
}
return stack.peek();
}
private static int calculate(int one, int two, char operator){
switch(operator){
case '+':
return one + two;
case '-':
return one - two;
case '*':
return one * two;
case '/':
return one / two;
case '^':
return (int)Math.pow(one, two);
}
return 0;
}
public static void main(String[] args) {
String expression = "9-3*2^2/3+1";//6
expression = MyStack.convert2Postfix(expression);
System.out.println(MyStack.calculatePostfixExpression(expression));//6
}
}
这是对不仅仅是单个数字的实现，对上面这个MyStack的补充
package com.eric.calculator;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class MyStack {
public static boolean checkBalance(String expression){
boolean balanced = true;
Stack<Character> stack = new Stack<Character>();
for(int i=0;balanced && i<expression.length();i++){
char ch = expression.charAt(i);
switch(ch){
case '(': case '[': case '{':
stack.push(ch);
break;
case ')': case ']': case '}':
if(stack.isEmpty()){
balanced = false;
}else{
char pop = stack.pop();
balanced = isPaired(pop,ch);
}
break;
}
}
if(!stack.isEmpty()){
balanced = false;
}
return balanced;
}
private static boolean isPaired(char left, char right){
return (left == '(' && right == ')') ||
(left == '[' && right == ']') ||
(left == '{' && right == '}');
}
/**
* 这里只考虑了在 0-9的整数
* 需要处理的数据类型包括：
* 运算数 ^ + - * / ( )
* 中缀表达式转变为后缀表达式时，遇到相应的符号所对应的动作：
* 运算数： 添加到输出表达式的末尾
* ^： 压入栈
* +-* /： 从栈中弹出运算符并添加到表达式的末尾，直到栈为空或者栈顶优先级比该新的运算符低。然后将新的运算符压入栈
* ( ： 压入栈
* ) ： 从栈中弹出运算符并添加到表达式的末尾，知道弹出(，丢弃这两个括号
* @param expression
* @return
*/
public static String convert2Postfix(String expression, String regex){
Stack<String> stack = new Stack<String>();
StringBuffer sb = new StringBuffer();
String[] arr = process(expression);
for(int i=0;i<arr.length;i++){
String ch = arr[i];
if(isDouble(ch)){
sb.append(ch + regex);
}else{
if(ch.equals("^")){
stack.push(ch);
} else if(ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/")){
while(!stack.isEmpty()){
String top = stack.peek();
if(getPrecedence(ch.charAt(0)) <= getPrecedence(top.charAt(0))){
sb.append(top + regex);
stack.pop();
}else{
break;
}
}
stack.push(ch);
} else if(ch.equals("(")){
stack.push(ch);
} else if(ch.equals(")")){
String pop = stack.pop();
while(!pop.equals("(")){
sb.append(pop + regex);
pop = stack.pop();
}
}
}
}
while(!stack.isEmpty()){
String pop = stack.pop();
sb.append(pop + regex);
}
return sb.toString();
}
private static int getPrecedence(char ch){
switch(ch){
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
default: return -1;
}
}
/**
* expression是中缀表达式
* @param regex
* @param expression
* @return
*/
public static double calculateExpression(String expression, String regex){
Stack<Double> stack = new Stack<Double>();
String[] arr = convert2Postfix(expression,regex).split(regex);
for(int i=0;i<arr.length;i++){
String ch = arr[i];
if(isDouble(ch)){
stack.push(Double.parseDouble(String.valueOf(ch)));
}else{
double two = stack.pop();
double one = stack.pop();
char operator = ch.charAt(0);
double value = calculate(one,two,operator);
stack.push(value);
}
}
return stack.peek();
}
private static double calculate(double one, double two, char operator){
switch(operator){
case '+':
return one + two;
case '-':
return one - two;
case '*':
return one * two;
case '/':
return one / two;
case '^':
return (int)Math.pow(one, two);
}
return 0;
}
/**
* 将expression处理下，以运算符来将expression分隔成数组
* @param expression
* @param index
* @return
*/
public static String[] process(String expression){
List<String> list = new ArrayList<String>();
char[] arr = expression.toCharArray();
StringBuffer sb = new StringBuffer();
for(int i=0;i<arr.length;i++){
if(arr[i] == '-'){//考虑到-不仅是减号，还有可能是负号
if(i == 0 || (arr[i-1] == '(' || arr[i-1] == ')' || arr[i-1] == '+' || arr[i-1] == '-' || arr[i-1] == '*' || arr[i-1] == '/')){
sb.append("-");
} else{
if(!sb.toString().trim().equals("")){
list.add(sb.toString());
}
list.add(String.valueOf(arr[i]));
sb = new StringBuffer();
}
} else if(arr[i] != '(' && arr[i] != ')' && arr[i] != '+' && arr[i] != '*' && arr[i] != '/' && arr[i] != '^' ){
sb.append(arr[i]);
} else{
if(!sb.toString().trim().equals("")){
list.add(sb.toString());
}
list.add(String.valueOf(arr[i]));
sb = new StringBuffer();
}
}
if(!sb.toString().trim().equals("")){//将最后的数据放入到list中
list.add(sb.toString());
}
return list.toArray(new String[list.size()]);
}
public static boolean isDouble(String input){
try {
Double.parseDouble(input);
return true;
} catch (NumberFormatException e) {
return false;
}
}
public static void main(String[] args) {
String regex = "_";
String expression = "(-9.0-3+6/3)*2^3/4+16";//-4
System.out.println(MyStack.convert2Postfix(expression, regex));
System.out.println(MyStack.calculateExpression(expression, regex));
// System.out.println(MyStack.checkBalance(expression));
}
}
5。 堆
6。 树
7。 图
分享到：
相关推荐
《Java数据结构与算法中文版》是一本深入探讨编程核心领域的书籍，主要针对Java程序员，旨在提升他们在数据处理和问题解决能力上的技能。这本书详细介绍了数据结构和算法的基础理论及其在Java语言中的实现，是Java...
《Java数据结构全套》是针对Java编程语言深入学习数据结构的重要资源集合，涵盖了从基本概念到高级应用的全面知识体系。这个压缩包包含了四部分关键内容：叶核亚编著的《数据结构（Java版）（第3版）》电子教案、...
根据提供的信息，“Java数据结构和算法中文第二版”这本书主要关注的是数据结构与算法的相关内容。下面将基于这些信息，详细介绍数据结构与算法的核心概念、重要性和应用领域，以及在Java编程环境中如何实现这些概念...
在本Java数据结构课程设计项目中，主要涵盖了数组、链表和字符串等基本数据结构的操作。这个项目不仅涉及了理论知识的应用，还实践了GUI（图形用户界面）的设计，使用了Swing库来构建用户交互界面，并利用文件系统...
"Java数据结构实例"这个主题，旨在通过具体的代码实例帮助初学者掌握数据结构的基本概念和使用方式，以此来提升编程思维和问题解决能力。在这个压缩包文件中，我们可以预期找到一些用Java实现的数据结构的源代码。 ...
《清华邓俊辉Java数据结构》是一门深入探讨数据结构及其在Java编程语言中实现的课程。这门课程由清华大学的邓俊辉教授主讲，旨在帮助学生掌握数据结构的基本概念，理解它们的工作原理，并能用Java语言进行实际操作。...
Java数据结构是计算机科学中的重要课程，主要探讨如何有效地存储和组织数据，以便进行高效的操作。这门课程通常包括数组、链表、栈、队列、树、图、哈希表等多种数据结构，并深入讲解它们的特性、操作方法以及在实际...
以上就是Java数据结构测试题中涉及的主要知识点，它们涵盖了数据结构、软件工程、面向对象编程和多线程等多个方面，这些都是Java开发者必备的基础知识。理解并掌握这些内容对于编写高效、安全的Java代码至关重要。
Java数据结构和算法是计算机科学中的核心概念，对于任何Java开发者来说，理解和掌握它们都是至关重要的。本资源包“Java数据结构和算法(第二版)+源代码+Applets”为学习者提供了一个全面且深入的学习平台，涵盖了...
Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法 Java数据结构和算法
《Java数据结构（老外那版，翻译的）》是一本专门为Java程序员设计的数据结构教程，它以清晰易懂的方式介绍了各种重要的数据结构概念。这本书是初学者的优秀选择，特别是对于那些偏好Java语言，不熟悉C++的人来说，...
Java数据结构是编程领域中的重要概念，它涉及如何在内存中高效地组织和管理数据，以便于快速访问和操作。本课件详细介绍了Java中常用的数据结构，包括数组、链表、栈、队列、树、图以及哈希表等。下面我们将逐一深入...
《Java数据结构和算法》（第2版）介绍了计算机编程中使用的数据结构和算法，对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章，分别讲述了基本概念、数组、简单排序、堆和...
java 数据结构总结的思维导图笔记，个人做的非常全，需要的自行下载
Java数据结构 线性表，链表，哈希表是常用的数据结构，在进行Java开发时，JDK已经为我们提供了一系列相应的类来实现基本的数据结构
本资源"JAVA数据结构与算法（中英全）"提供了一套完整的Java数据结构和算法的学习资料，包括中文和英文两个版本，方便不同语言背景的学习者使用。 首先，我们来探讨数据结构这一部分。数据结构是组织、管理、存储和...
Java 数据结构 Applet演示是利用Java编程语言设计的交互式应用程序，主要目的是通过可视化的方式帮助学习者理解数据结构的基本概念和操作。Applet是Java的一种小型应用程序，可以在Web浏览器中运行，提供了一种便捷...
Java数据结构和算法.pdf
Java数据结构是编程领域中的重要基础，它涉及如何在计算机中高效地组织和管理数据，以便进行快速查找、插入和删除等操作。本主题主要关注Java语言实现的数据结构及其相关算法，这对于提升程序性能和解决复杂问题至关...