Labels

Saturday, 20 July 2013

CalculatorModel.java
view sourceprint?
 
02// and that is it. It doesn't know the View
03// exists
04 
05public class CalculatorModel {
06 
07    // Holds the value of the sum of the numbers
08    // entered in the view
09     
10    private int calculationValue;
11     
12    public void addTwoNumbers(int firstNumber, int secondNumber){
13         
14        calculationValue = firstNumber + secondNumber;
15         
16    }
17    
18    public int getCalculationValue(){
19         
20        return calculationValue;
21         
22    }
23     
24}

CalculatorView.java
view sourceprint?
01// This is the View
02// Its only job is to display what the user sees
03// It performs no calculations, but instead passes
04// information entered by the user to whomever needs
05// it.
06 
07import java.awt.event.ActionListener;
08 
09import javax.swing.*;
10 
11public class CalculatorView extends JFrame{
12 
13    private JTextField firstNumber  = new JTextField(10);
14    private JLabel additionLabel = new JLabel("+");
15    private JTextField secondNumber = new JTextField(10);
16    private JButton calculateButton = new JButton("Calculate");
17    private JTextField calcSolution = new JTextField(10);
18     
19    CalculatorView(){
20         
21        // Sets up the view and adds the components
22         
23        JPanel calcPanel = new JPanel();
24         
25        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
26        this.setSize(600, 200);
27         
28        calcPanel.add(firstNumber);
29        calcPanel.add(additionLabel);
30        calcPanel.add(secondNumber);
31        calcPanel.add(calculateButton);
32        calcPanel.add(calcSolution);
33         
34        this.add(calcPanel);
35         
36        // End of setting up the components --------
37         
38    }
39     
40    public int getFirstNumber(){
41         
42        return Integer.parseInt(firstNumber.getText());
43         
44    }
45     
46    public int getSecondNumber(){
47         
48        return Integer.parseInt(secondNumber.getText());
49         
50    }
51     
52    public int getCalcSolution(){
53         
54        return Integer.parseInt(calcSolution.getText());
55         
56    }
57     
58    public void setCalcSolution(int solution){
59         
60        calcSolution.setText(Integer.toString(solution));
61         
62    }
63     
64    // If the calculateButton is clicked execute a method
65    // in the Controller named actionPerformed
66     
67    void addCalculateListener(ActionListener listenForCalcButton){
68         
69        calculateButton.addActionListener(listenForCalcButton);
70         
71    }
72     
73    // Open a popup that contains the error message passed
74     
75    void displayErrorMessage(String errorMessage){
76         
77        JOptionPane.showMessageDialog(this, errorMessage);
78         
79    }
80     
81}

CalculatorController.java
view sourceprint?
01import java.awt.event.ActionEvent;
02import java.awt.event.ActionListener;
03 
04// The Controller coordinates interactions
05// between the View and Model
06 
07public class CalculatorController {
08     
09    private CalculatorView theView;
10    private CalculatorModel theModel;
11     
12    public CalculatorController(CalculatorView theView, CalculatorModel theModel) {
13        this.theView = theView;
14        this.theModel = theModel;
15         
16        // Tell the View that when ever the calculate button
17        // is clicked to execute the actionPerformed method
18        // in the CalculateListener inner class
19         
20        this.theView.addCalculateListener(new CalculateListener());
21    }
22     
23    class CalculateListener implements ActionListener{
24 
25        public void actionPerformed(ActionEvent e) {
26             
27            int firstNumber, secondNumber = 0;
28             
29            // Surround interactions with the view with
30            // a try block in case numbers weren't
31            // properly entered
32             
33            try{
34             
35                firstNumber = theView.getFirstNumber();
36                secondNumber = theView.getSecondNumber();
37                 
38                theModel.addTwoNumbers(firstNumber, secondNumber);
39                 
40                theView.setCalcSolution(theModel.getCalculationValue());
41             
42            }
43 
44            catch(NumberFormatException ex){
45                 
46                System.out.println(ex);
47                 
48                theView.displayErrorMessage("You Need to Enter 2 Integers");
49                 
50            }
51             
52        }
53         
54    }
55     
56}

MVCCalculator.java
view sourceprint?
01public class MVCCalculator {
02     
03    public static void main(String[] args) {
04         
05        CalculatorView theView = new CalculatorView();
06         
07        CalculatorModel theModel = new CalculatorModel();
08         
09        CalculatorController theController = new CalculatorController(theView,theModel);
10         
11        theView.setVisible(true);
12         
13    }
14}

http://www.newthinktank.com/2013/02/mvc-java-tutorial/
- See more at: http://www.newthinktank.com/2013/02/mvc-java-tutorial/#sthash.uSKCsfhx.dpuf
Posted by at No comments:

Friday, 19 July 2013

Các nguyên lý lập trình hướng đối tượng

Từ hôm nay, để trợ giúp cho các nhóm phân tích, thiết kế và lập trình các dự án tại TT, tôi sẽ cố gắng đưa nhiều bài viết ( sưu tầm là chính ) để mọi người cùng tham khảo.

Đề nghị mọi người đóng góp nhiều hơn cho chuyên mục này để cùng nâng cao chuyên môn. Sang năm 2007, một trong những trọng tâm của phòng TKHT là xây dựng tài nguyên dùng chung để tái sử dụng các sản phẩm đã làm từ khâu phân tích, thiết kế đến lập trình.

Tôi xin đưa bài thứ nhất : Các nguyên lý lập trình hướng đối tượngPhương pháp lập trình hướng đối tượng đã được nghiên cứu và phát triển từ lâu nhưng việc vận dụng nó như thế nào cho hiệu quả trong việc xây dựng phần mềm là điều vẫn còn khá mơ hồ đối với nhiều người. Thế nào là một phần mềm hướng đối tượng? Đâu là những cơ sở nền tảng để xây dựng được phần mềm theo tư tưởng hướng đối tượng đúng nghĩa? Trong bài viết này, trình bày về các nguyên lý lập trình hướng đối tượng. Đó là những quy tắc phân tích thiết kế hướng đối tượng cơ bản, mang tính chất khái quát. Nó được xem như "kim chỉ nam" soi đường dẫn lối cho chúng ta khi tiến hành phân tích thiết kế theo tư tưởng hướng đối tượng. Do là nguyên lý nên nó có tính trừu tượng cao chứ không đi vào chi tiết cách thức giải quyết vấn đề cụ thể (việc hiện thực hóa những nguyên lý lập trình hướng đối tượng đòi hỏi chúng ta phải xem xét đến Design Patterns)

Các nguyên lý lập trình hướng đối tượng (The OOP Principles)

Nguyên lý Open-Closed

(The Open-Closed Principle)


Phát biểu

Các thực thể phần mềm (hàm, đơn thể, đối tượng, …) nên được xây dựng theo hướng mở cho việc mở rộng (be opened for extension) nhưng đóng đối với việc sửa đổi (be closed for modification).
Nội dung

Các thực thể trong một phần mềm không đứng riêng lẻ mà có sự gắn kết chặt chẽ với nhau. Chúng phối hợp hoạt động để cùng nhau thực hiện các chức năng của phần mềm. Do đó, việc nâng cấp, mở rộng một thực thể nào đó sẽ ảnh hưởng đến những thực thể liên quan. Điều này có thể dẫn đến việc phải nâng cấp, mở rộng cả những thực thể liên quan đó. Và trong thời đại đầy biến động hiện nay, việc phải thường xuyên nâng cấp, mở rộng các thực thể trong phần mềm là điều khó tránh khỏi.
Để làm cho quá trình bảo trì, nâng cấp, mở rộng phần mềm diễn ra dễ dàng và hiệu quả hơn, các thực thể phần mềm nên được xây dựng tuân theo nguyên lý Open-Closed. Điều này có nghĩa là các thực thể phần mềm nên được xây dựng sao cho việc nâng cấp, mở rộng đồng nghĩa với việc thêm vào những cái mới chứ không phải là thay đổi những cái hiện có, từ đó tránh được việc phải thay đổi các thực thể liên quan.
Xét ví dụ một đoạn chương trình vẽ đường thẳng và hình chữ nhật bằng C#.
public enum ShapeType
{
LINE,
RECTANGLE
}
public abstract class Shape
{
public abstract ShapeType getType();
}
public class Line: Shape
{
public override ShapeType getType()
{
return ShapeType.LINE;
}
public void drawLine()
{
// Draws the line...
}
}
public class Rectangle: Shape
{
public override ShapeType getType()
{
return ShapeType.RECTANGLE;
}
public void drawRectangle()
{
// Draws the rectangle...
}
}
public void draw(ArrayList shapeList)
{
Line line;
Rectangle rectangle;
foreach (Shape s in shapeList)
switch (s.getType())
{
case ShapeType.LINE:
line = (Line)s;
line.drawLine();
break;
case ShapeType.RECTANGLE:
rectangle = (Rectangle)s;
rectangle.drawRectangle();
break;
}
}
Đoạn chương trình trên hoạt động rất tốt cho đến khi có sự nâng cấp, mở rộng. Giả sử chúng ta cần nâng cấp, mở rộng đoạn chương trình trên để nó có thể vẽ thêm được hình tròn. Lúc bấy giờ ta phải chỉnh sửa lại hàm “draw”, thêm vào một trường hợp vẽ hình tròn. Và trong nhiều tình huống, việc chỉnh sửa hàm “draw” sẽ dẫn đến việc chỉnh sửa những hàm khác liên quan. Hàm “draw” được viết theo cách này được nói là không tuân thủ nguyên lý Open-Closed.
Để đoạn chương trình trên tuân thủ nguyên lý Open-Closed, chúng ta sử dụng tính đa hình của lập trình hướng đối tượng.
public abstract class Shape
{
public abstract void draw();
}
public class Line: Shape
{
public override void draw()
{
// Draws the line...
}
}
public class Rectangle: Shape
{
public override void draw()
{
// Draws the rectangle...
}
}
class Circle: Shape
{
public override void draw()
{
// Draws the circle...
}
}

public void draw(ArrayList shapeList)
{
foreach (Shape s in shapeList)
s.draw();
}
Với đoạn chương trình trên, khi thêm một hình mới vào, chúng ta chỉ việc thêm lớp đối tượng cho hình đó (kế thừa từ Shape) mà không cần phải chỉnh sửa lại hàm “draw”. Nó vẫn hoạt động tốt với những hình mới thêm vào.
Ghi chú

i) Không phải lúc nào tất cả các thực thể trong phần mềm đều có thể tuân thủ nguyên lý Open-Closed. Nhưng mục tiêu của phân tích thiết kế hướng đối tượng là phải làm sao cho số lượng các thực thể tuân thủ nguyên lý là lớn nhất, trong đó ưu tiên các thực thể thường xuyên phải nâng cấp, mở rộng thỏa nguyên lý.
ii) Việc tuân thủ nguyên lý Open-Closed của một thực thể phần mềm chỉ mang tính tương đối, phụ thuộc vào ngữ cảnh. Có thể trong ngữ cảnh này, thực thể thỏa nguyên lý, nhưng trong một ngữ cảnh khác, thực thể này không còn tuân thủ nguyên lý nữa. Mục tiêu của phân tích thiết kế hướng đối tượng là phải làm sao cho có nhiều thực thể phần mềm nhất tuân thủ nguyên lý trong ngữ cảnh thường xảy ra nhất của phần mềm, trong đó ưu tiên các thực thể thường xuyên phải nâng cấp, mở rộng thỏa nguyên lý.
Ví dụ trường hợp hàm “draw” như trong đoạn chương trình vẽ hình trên.
public void draw(ArrayList shapeList)
{
foreach (Shape s in shapeList)
s.draw();
}
Hàm “draw” chỉ thỏa nguyên lý trong ngữ cảnh nâng cấp mở rộng là “thêm hình mới”. Nếu chúng ta cần nâng cấp, mở rộng theo hướng thay đổi thứ tự vẽ các hình thì hàm “draw” như trên là không thể đáp ứng được. Khi đó nó không còn tuân thủ nguyên lý nữa.
iii) Một tính chất quan trọng trong lập trình hướng đối tượng giúp cho các thực thể phần mềm tăng khả năng tuân thủ nguyên lý Open-Closed là tính đóng gói (encapsulation). Đối tượng nắm giữ thông tin và chịu trách nhiệm trên thông tin mình nắm giữ. Điều này giúp hạn chế sự kết dính (coupling) giữa các lớp đối tượng với nhau. Trường hợp lý tưởng là tất cả thuộc tính của đối tượng được đặt tầm vực private. việc thay đổi trên thuộc tính chỉ có thể được thực hiên thông qua những xử lý của phương thức. Những phương thức của đối tượng khác, kể cả đối tượng kế thừa không thể truy xuất được đến những thuộc tính này.
iv) Việc hạn chế sử dụng ép kiểu động (runtime type-casting) trong các thực thể phần mềm cũng sẽ giúp làm tăng khả năng tuân thủ nguyên lý Open-Closed của chúng. Vì bản chất của việc ép kiểu động là làm việc với một kiểu dữ liệu cụ thể. Khi muốn nâng cấp, mở rộng thực thể để nó có thể làm việc với những kiểu dữ liệu khác, đoạn chương trình sử dụng ép kiểu động phải được thay đổi để có thể làm việc được với các kiểu dữ liệu khác này.
public void doSomething(Vehicle vehicle)
{
Car car = (Car)vehicle;
car.run();
car.stop();
}
Khi cần nâng cấp, mở rộng để đoạn chương trình trên có thể làm việc được với các lớp đối tượng khác kế thừa từ “Vehicle”, chúng ta phải chỉnh sửa lại nó.
Ý nghĩa

Nguyên lý Open-Closed là nguyên lý cốt lõi và là một trong bốn nguyên lý cơ bản làm nền tảng cho phân tích thiết kế hướng đối tượng. Nó giúp cho phần mềm dễ bảo trì, nâng cấp và mở rộng.

Nguyên lý Nghịch đảo phụ thuộc

(The Dependency Inversion Principle) Phát biểu

Các thành phần trong phần mềm không nên phụ thuộc vào những cái riêng, cụ thể (details) mà ngược lại nên phụ thuộc vào những cái chung, tổng quát (abstractions) của những cái riêng, cụ thể đó.
Những cái chung, tổng quát (abstractions) không nên phụ vào những cái riêng, cụ thể (details). Sự phụ thuộc này nên được đảo ngược lại.
Nội dung

Những cái chung, tổng quát là tập hợp của những đặc tính chung nhất từ những cái riêng, cụ thể. Những cái riêng, cụ thể dù khác nhau thế nào đi nữa cũng đều tuân theo các quy tắc chung mà cái chung, tổng quát của nó đã định nghĩa. Những cái chung, tổng quát là những cái ít thay đổi và ít biến động. Trong khi đó, sự thay đổi lại thường xuyên xảy ra ở những cái riêng, cụ thể. Việc phụ thuộc vào những cái chung, tổng quát sẽ giúp cho các thành phần trong phần mềm trở nên linh động (flexible) và thích ứng tốt với sự thay đổi thường xuyên diễn ra ở những cái riêng, cụ thể. Khi phụ thuộc vào những cái chung, tổng quát, các thành phần trong phần mềm vẫn có thể hoạt động tốt mà không cần phải sửa đổi một khi cái riêng, cụ thể được thay thế bằng một cái riêng, cụ thể khác cùng loại.
Lấy ví dụ đoạn chương trình đọc dữ liệu từ bàn phím và xuất ra máy in.
public void copy()
{
Keyboard keyboard = new Keyboard();
Printer printer = new Printer();
char c;
while ((c = keyboard.read()) != ‘q’)
printer.write(c);
}
Khi nâng cấp, mở rộng đoạn chương trình trên để nó có thể xuất dữ liệu ra máy in hoặc tập tin thì chúng ta phải chỉnh sửa lại đoạn chương trình trên như sau.
public void copy(OutputType type)
{
Keyboard keyboard = new Keyboard();
Printer printer = new Printer();
File file = new File();
char c;
while ((c = keyboard.read()) != ‘q’)
if (type == OutputType.PRINTER)
printer.write(c);
else if (type == OutputType.FILE)
file.write(c);
}
Rõ ràng hàm “copy” như trên đã vi phạm nguyên lý Open-Closed do khi mỗi lần cần thêm một thiết bị đọc ghi mới vào, chúng ta phải chỉnh sửa lại nó. Nguyên nhân làm cho hàm “copy” vi phạm nguyên lý Open-Closed là do nó làm việc với từng thiết bị đọc ghi cụ thể. Khi thêm một thiết bị đọc ghi mới, chúng ta phải thêm vào hàm “copy” đoạn lệnh để làm việc với thiết bị đọc ghi mới. Khi đó chúng ta nói hàm “copy” vi phạm nguyên lý Nghịch đảo phụ thuộc.
Để đoạn chương trình trên tuân thủ Nguyên lý Nghịch đảo phụ thuộc, từ đó tuân thủ Nguyên lý Open-Closed, chúng ta phải cho nó làm việc với thiết bị đọc ghi tổng quát.
public void copy(Reader reader, Writer writer)
{
char c;
while ((c = reader.read()) != ‘q’)
writer.write(c);
}
Hàm “copy” như trên có thể làm việc tốt với bất kỳ thiết bị đọc ghi nào tuân thủ interface của Reader và Writer. Khi cần thêm thiết bị đọc ghi mới, chúng ta chỉ việc thêm lớp đối tượng kế thừa từ Reader hoặc Writer mà không phải chỉnh sửa lại hàm “copy”.
Trích lời Allen Holub: “The more abstraction you add, the greater the flexibility. In today’s business environment, where requirements regularly change as program develops, this flexibility is essential.”.
Chú ý

i) Nguyên lý Nghịch đảo phụ thuộc có mối liên hệ mật thiết với nguyên lý Open-Closed. Một khi nguyên lý Nghịch đảo phụ thuộc bị vi phạm, có nghĩa là những thành phần trong phần mềm phụ thuộc vào những cái riêng, cụ thể, việc nâng cấp, mở rộng ở những cái riêng, cụ thể (điều này rất thường xảy ra) buộc những thành phần phụ thuộc vào nó bị thay đổi theo. Điều này dẫn đến vi phạm nguyên lý Open-Closed.
ii) Sự nghịch đảo được đề cập đến ở đây nhằm nhấn mạnh đến việc cần phải thay đổi quan điểm trong phân tích thiết kế phần mềm. Theo lối suy nghĩ “chia để trị” của lập trình hướng cấu trúc, những công việc lớn, phức tạp, mang tính trừu tượng cao thường được phân ra thành những công việc nhỏ, đơn giản và cụ thể hơn. Khi đó, cấu trúc phần mềm có xu hướng theo dạng những thành phần lớn (trừu tượng) gọi đến những thành phần nhỏ (cụ thể) hơn để yêu cầu chúng thực hiện công việc. Điều này thường làm cho những thành phần trong phần mềm phụ thuộc vào những cái riêng, cụ thể. Trong phân tích thiết kế hướng đối tượng, sự phụ thuộc này nên được đảo ngược lại.
iii) Một thành phần trong phần mềm vi phạm nguyên lý Nghịch đảo phụ thuộc sẽ có tính tái sử dụng (reusability) không cao. Việc mang những thành phần này sử dụng vào một ngữ cảnh khác với những cái riêng, cụ thể khác là khó có thể thực hiện được nếu như không thực hiện việc chỉnh sửa nào trên chúng.
iv) Một quy ước trong lập trình hướng đối tượng giúp cho các thành phần trong phần mềm tăng khả năng tuân thủ nguyên lý Nghịch đảo phụ thuộc là thực hiện việc truy xuất đến các đối tượng thông qua interface của chúng. Điều này sẽ làm cho các thành phần bên trong phần mềm có tính linh động (flexibility) cao, không phải sửa đổi khi thay thế các đối tượng được truy xuất đến bằng đối tượng khác cùng loại.
public void doSomething(Car car)
{
car.run();
car.stop();
}
public void doSomething(Vehicle vehicle)
{
vehicle.run();
vehicle.stop();
}
Trong hai đoạn chương trình trên, đoạn chương trình thứ hai vẫn làm việc tốt khi chúng ta thêm vào các đối tượng khác cùng loại với “Car” mà kế thừa từ “Vehicle”.
Ý nghĩa

Nguyên lý Nghịch đảo phụ thuộc có mối liên hệ mật thiết với nguyên lý Open-Closed và là một trong bốn nguyên lý cơ bản làm nền tảng cho phân tích thiết kế hướng đối tượng. Nó giúp cho phần mềm có tính tái sử dụng cao, linh động và bền vững (robustness) trước những sự thay đổi.

Nguyên lý Thay thế Liskov

(The Liskov Substitution Principle)



Phát biểu

Lớp B chỉ nên kế thừa từ lớp A khi và chỉ khi với mọi hàm F thao tác trên các đối tượng của A, cách cư xử (behaviors) của F không thay đổi khi ta thay thế (substitute) các đối tượng của A bằng các đối tượng của B.
Nội dung

Kế thừa (inheritance) là một trong những tính chất cơ bản của lập trình hướng đối tượng. Đó là khả năng định nghĩa một lớp đối tượng dựa trên các lớp đối tượng đã được định nghĩa trước đó. Các đối tượng của lớp kế thừa có khả năng cư xử (behave) như các đối tượng của lớp cơ sở. Điều này có nghĩa là các đối tượng của lớp kế thừa hoàn toàn có thể thay thế các đối tượng của lớp cơ sở trong những hàm thao tác trên các đối tượng của lớp cơ sở.
Chính vì tính chất này mà chúng ta không thể sử dụng kế thừa một cách tùy tiện. Giả sử ta có lớp A và hàm F thao tác trên các đối tượng của A. Để nâng cấp, mở rộng phần mềm, ta cần thêm vào lớp B kế thừa từ A. Nhưng việc thay thế các đối tượng của A bằng các đối tượng của B lại làm cho F cư xử sai lệch so với trước khi thực hiện việc thay thế. Lúc này, để F có thể cư xử không đổi so với trước, ta phải chỉnh sửa lại F. Điều này làm cho F vi phạm nguyên lý Open-Closed.
Đoạn chương trình sau cho thấy việc kế thừa tùy tiện chỉ với mục đích tái sử dụng nguy hiểm như thế nào.
public class Stack
{
private ArrayList data;
// More data members of stack.
public virtual void push(int n)
{
// Pushes n to stack...
}
public virtual int pop()
{
// Pops value from stack...
}
}
public class Queue: Stack
{
// Data members of Queue.
public override void push(int n)
{
// Pushes n to queue...
}
public override int pop()
{
// Pops value from queue...
}
}
public int func(Stack p)
{
p.push(5);
p.push(6);
p.push(7);
int a = p.pop();
int b = p.pop();
if (a == 7 && b == 6)
return a * b;
throw new ArgumentException();
}
Với mục đích tái sử dụng là một số thuộc tính và phương thức trong “Stack”, chúng ta cho “Queue” kế thừa từ Stack. Xét hàm “func” thao tác trên đối tượng của “Stack”, do “Queue” kế thừa từ “Stack” nên chúng ta hoàn toàn có thể truyền đối tượng của “Queue” vào hàm này. Nhưng cách cư xử của hàm “func” khi thao tác trên các đối tượng của “Stack” và “Queue” là khác nhau. Với các đối tượng của “Stack” hàm func luôn trả về chính xác tích của hai số 7 và 6. Nhưng với các đối tượng của “Queue” hàm func lại luôn gây ra một exception. Để hàm “func” có thể cư xử trên các đối tượng của “Stack” và “Queue” như nhau, chúng ta phải viết lại nó. Điều này làm cho hàm “func” vi phạm nguyên lý Open-Closed. Khi đó ta nói hàm “func” vi phạm nguyên lý Thay thế Liskov.
Chú ý

i) Nguyên lý Thay thế Liskov có mối liên hệ mật thiết với Nguyên lý Open-Closed. Sự vi phạm nguyên lý Thay thế Liskov sẽ dẫn đến sự vi phạm nguyên lý Open-Closed. Một thực thể phần mềm vi phạm nguyên lý Thay thế Liskov sẽ cư xử khác nhau trên các đối tượng của lớp cơ sở và lớp kế thừa. Để thực thể phần mềm này vẫn có thể làm việc tốt trên các đối tượng của cả lớp cơ sở và lớp kế thừa, chúng ta phải chỉnh sửa lại nó. Điều này dẫn đến vi phạm nguyên lý Open-Closed.
ii) Không phải lúc nào tất cả các thực thể trong phần mềm đều có thể tuân thủ nguyên lý Thay thế Liskov. Nhưng mục tiêu của phân tích thiết kế hướng đối tượng là phải làm sao cho số lượng các thực thể tuân thủ nguyên lý là lớn nhất, trong đó ưu tiên các thực thể thường xuyên phải nâng cấp, mở rộng thỏa nguyên lý.
iii) Việc tuân thủ nguyên lý Thay thế Liskov của một thực thể phần mềm chỉ mang tính tương đối, phụ thuộc vào ngữ cảnh. Có thể trong ngữ cảnh này, thực thể thỏa nguyên lý, nhưng trong một ngữ cảnh khác, thực thể này không còn tuân thủ nguyên lý nữa. Mục tiêu của phân tích thiết kế hướng đối tượng là phải làm sao cho có nhiều thực thể phần mềm nhất tuân thủ nguyên lý trong ngữ cảnh thường xảy ra nhất của phần mềm, trong đó ưu tiên các thực thể thường xuyên phải nâng cấp, mở rộng thỏa nguyên lý.
iv) Quan hệ “IS-A” thường được dùng để phát hiện kế thừa. Khi lớp đối tượng B về mặt ngữ nghĩa là một trường hợp đặc biệt của lớp đối tượng A thì ta có thể cho B kế thừa từ A. Nhưng thực tế cho thấy, trong một số ngữ cảnh của phần mềm, một lớp đối tượng có quan hệ “IS-A” với những lớp đối tượng khác nhưng việc để nó kế thừa những lớp đối tượng này sẽ dẫn đến việc vi phạm nguyên lý Thay thế Liskov.
Xét đoạn chương trình sau.
public class Rectangle
{
// Data members of rectangle...
// Member functions of rectangle...
}
public class Square: Rectangle
{
// Data members of square...
// Member functions of square...
}
public double doSomething(Rectangle obj)
{
obj.setWidth(5);
obj.setHeight(6);
if (obj.Area == 30)
return obj.Area;
throw new ArgumentException();
}
Ở đoạn chương trình trên, mặc dù về mặt ngữ nghĩa, hình vuông là một trường hợp của hình chữ nhật. Điều này hoàn toàn đúng!!! Nhưng trong ngữ cảnh này, việc để “Square” kế thừa “Rectangle” là không phù hợp. Lúc này hàm “doSomething” cư xử khác nhau trên các đối tượng của “Rectangle” và “Square”. Như vậy hàm “doSomething” đã vi phạm nguyên lý Thay thế Liskov. Để hàm “doSomething” có thể làm việc được trên cả “Rectangle” và “Square” chúng ta phải chỉnh sửa lại nó. Như vậy việc vi phạm nguyên lý Thay thế Liskov đã làm cho hàm “doSomething” vi phạm nguyên lý Open-Closed.
v) Nguyên lý Thay thế Liskov có mối liên hệ mật thiết với kỹ thuật “Design by Contract” được đề cập bởi Bertrand Meyers. Kỹ thuật này chỉ ra rằng: mỗi phương thức trong một lớp đối tượng, khi được định nghĩa, đã hàm chứa trong nó tiền điều kiện (pre-condition) và hậu điều kiện (post-condition). Tiền điều kiện là những điều kiện cần để phương thức có thể thực hiện được. Hậu điều kiện là những ràng buộc phát sinh sau khi thực hiện phương thức. Khi thực hiện việc kế thừa, phương thức được định nghĩa lại trong lớp kế thừa phải có tiền điều kiện lỏng lẻo hơn (weaker) và hậu điều kiện chặt chẽ hơn (stronger). Điều này có nghĩa là trước khi thực hiện, phương thức được định nghĩa lại trong lớp kế thừa không được đòi hỏi nhiều hơn như khi nó được định nghĩa trong lớp cơ sở. Và sau khi thực hiện, phương thức được định nghĩa lại trong lớp kế thừa phải đảm bảo tất cả những ràng buộc phát sinh như khi nó được định nghĩa trong lớp cơ sở. Chỉ khi nào những điều trên được đáp ứng cho mọi phương thức trong lớp kế thừa thì lớp kế thừa mới được xem là cư xử như lớp cơ sở. Và khi đó, việc để nó kế thừa từ lớp cơ sở mới là đúng đắn trong ngữ cảnh phần mềm đang xét.
vi) Nguyên lý Thay thế Liskov và kỹ thuật “Design by Contract” vô tình làm cho việc kế thừa trở nên rất khó thực hiện. Khi cần thêm vào một lớp kế thừa, chúng ta phải xem xét rất kỹ lưỡng lại tất cả hàm có thao tác trên lớp cơ sở xem chúng có vi phạm nguyên lý Thay thế Liskov hay không. Chúng ta cũng cần phải xem xét tất cả các phương thức của lớp kế thừa xem chúng có vi phạm những quy định của kỹ thuật “Design by Contract” hay không. Tất cả những điều này là do lớp kế thừa có một mối liên hệ mật thiết với lớp cơ sở. Lớp kế thừa bị kết dính (coupling) chặt chẽ với lớp cơ sở. Sự kết dính này rõ ràng làm cho phần mềm kém linh động (flexibility) một khi có sự thay đổi xảy ra. Do đó, để hạn chế sự kết dính này mà vẫn đảm bảo được tính tái sử dụng, chúng ta chỉ nên kế thừa interface và sử dụng composition thay cho việc kế thừa.
Ý nghĩa

Nguyên lý Thay thế Liskov có mối liên hệ mật thiết với nguyên lý Open-Closed và là một trong bốn nguyên lý cơ bản làm nền tảng cho phân tích thiết kế hướng đối tượng. Nó giúp nâng cao tính tái sử dụng và bền vững của phần mềm trước những sự thay đổi.

Nguyên lý Phân tách interface

(The Interface Segregation)

Phát biểu

Không nên buộc các thực thể phần mềm phụ thuộc vào những interface mà chúng không sử dụng đến.

Nội dung

Khi xây dựng một lớp đối tượng, đặc biệt là những lớp trừu tượng (abstract class), nhiều người thường có xu hướng để cho lớp đối tượng thực hiện càng nghiều chức năng càng tốt, đưa thật nhiều thuộc tính và phương thức vào lớp đối tượng đó. Những lớp đối tượng như vậy được gọi là những lớp đối tượng có interface bị “ô nhiễm” (fat interface or polluted interface).

Khi một lớp đối tượng có interface bị “ô nhiễm”, nó sẽ trở nên cồng kềnh. Một thực thể phần mềm nào đó chỉ cần thực hiện một công việc đơn giản mà lớp đối tượng này hỗ trợ buộc phải làm việc với toàn bộ interface của lớp đối tượng đó. Việc phải truyền đi truyền lại nhiều lần những đối tượng có interface bị “ô nhiễm” sẽ làm giảm hiệu năng của phần mềm.

Đặc biệt đối với lớp trừu tượng có interface bị “ô nhiễm”, một số lớp kế thừa chỉ quan tâm đến một phần interface của lớp cơ sở nhưng bị buộc phải thực hiện việc cài đặt cho cả phần interface không hề có ý nghĩa đối với chúng. Điều này dẫn đến sự dư thừa không cần thiết trong các thực thể phần mềm. Quan trọng hơn nữa, việc buộc các lớp kế thừa phụ thuộc vào phần interface mà chúng không sử dụng đến sẽ làm tăng sự kết dính (coupling) giữa các thực thể phần mềm. Một khi sự nâng cấp, mở rộng diễn ra, đòi hỏi phần interface đó phải thay đổi, các lớp kế thừa này bị buộc phải chỉnh sửa theo. Điều này làm cho chúng vi phạm nguyên lý Open-Closed.

Hình bên dươi là sơ đồ lớp cho đoạn chương trình tính điện trở mạch điện. “Resistor” và “Lamp” là những mạch điện đơn giản với điện trở là một thuộc tính của mạch. Trong khi “SeriesCircuit” và “ParallelCircuit” là những mạch điện phức hợp với điện trở của mạch được tính từ các mạch điện con. Để có thể cư xử như nhau trên các loại mạch điện này hay nói cách khác là truy xuất đến chúng một cách “trong suốt” (transparency), chúng ta có “Circuit” là lớp trừu tượng chung đại diện cho các mạch điện khác nhau.

Lớp “Circuit” được thiết kế như trên được gọi là có interface bị “ô nhiễm”. “Resistor” và “Lamp” bị buộc phải thực hiện việc cài đặt cho các phương thức “add” và “remove” hoàn toàn chẳng có ý nghĩa gì với chúng. Điều này gây ra sự dư thừa code không cần thiết cũng như gây “khó chịu” cho những thực thể phần mềm khác sử dụng “Resistor” và “Lamp”.

Nhưng vấn đề chỉ thật sự xảy ra khi chúng ta nâng cấp, mở rộng đoạn chương trình trên. Giả sử chúng ta cần thêm vào phương thức “removeAt” để hỗ trợ việc xóa mạch điện con tại vị trí nào đó trong mạch điện phức hợp. Lúc này, chúng ta phải thực hiện việc chỉnh sửa trên tất cả các lớp đối tượng kế thừa từ “Circuit”. Việc chỉnh sửa trên “SeriesCircuit” và “ParallelCircuit” xem ra còn có thể chấp nhận được. Nhưng việc phải chỉnh sửa trên “Resistor” và “Lamp” là không thể chấp nhận được vì phương thức “removeAt” chẳng hề có ý nghĩa gì đối với chúng. Điều này rõ ràng làm cho “Resistor” và “Lamp” vi phạm nguyên lý Open-Closed một cách “không chính đáng”.

Chú ý

i) Nguyên lý Phân tách interface có mối liên hệ với nguyên lý Open-Closed. Sự vi phạm nguyên lý Phân tách interface có khả năng dẫn đến sự vi phạm nguyên lý Open-Closed (xem phân tích ở trên).

ii) Để tránh vi phạm nguyên lý Phân tách Inteface, chúng ta nên giữ cho interface của lớp đối tượng đơn giản và gọn nhẹ, nên làm theo tiêu chí “a class should do one thing and do it well”. Chúng ta không nên để cho lớp đối tượng đảm nhận quá nhiều trách nhiệm vì điều này dễ làm cho interface của nó bị “ô nhiễm”.

iii) Interface bị “ô nhiễm” của lớp đối tượng nên được phân tách ngay khi có thể để tránh khả năng dẫn đến sự vi phạm nguyên lý Open-Closed. Việc phân tách interface bị “ô nhiễm” của một lớp cơ sở có thể được thực hiện thông qua việc tăng thêm mức độ trừu tượng trong cây kế thừa của nó. Lớp cơ sở ban đầu chỉ nên có interface đơn giản mà mọi lớp kế thừa của nó đều cần phải có. Sau đó, phần interface chung của một bộ phận lớp kế thừa được tổng hợp lại trong một lớp cơ sở. Và lớp cơ sở này lại kế thừa từ lớp cơ sở ban đầu. Như vậy những lớp kế thừa thuộc nhánh khác không bị phụ thuộc vào phần interface mà chúng không sử dụng đến của bộ phận lớp kế thừa kia.

Với trường hợp đoạn chương trình tính điện trở mạch điện, để giải quyết vấn đề interface của “Circuit” bị “ô nhiễm”, chúng ta tăng thêm một mức độ trừu tượng trong cây kế thừa của nó. Khi đó, “Circuit” đóng vai trò là lớp trừu tượng cho các mạch điện khác nhau. Nó chỉ chứa phần interface chung nhất của tất cả các mạch điện này. Và trong ngữ cảnh bài toán tính điện trở đơn giản thì nó chỉ chứa phương thức “calcResistance”.

Chúng ta sẽ có lớp “SingleCircuit” đại diện cho các mạch điện đơn giản và “ComplexCircuit” đại diện cho cách mạch điện phức hợp. “SingleCircuit” chứa phần interface chung của các mạch điện đơn giản như “Resistor” và “Lamp” trong khi “ComplexCircuit” chứa phần interface chung của các mạch điện phức hợp. Chúng ta sẽ có được cây kế thừa như hình bên dưới.

Lúc này, khi cần thêm vào phương thức “removeAt” chúng ta chỉ việc nâng cấp phần interface của “ComplexCircuit”, nhánh kế thừa bên “SingleCircuit” sẽ không bị ảnh hưởng.

iv) Trong một số trường hợp, sau khi phân tách interface, một số lớp kế thừa mới thêm vào muốn sử dụng những phần interface đã phân tách, chúng có thể thực hiện việc đa kế thừa từ những lớp đối tượng hỗ trợ những phần interface này hoặc cũng có thể kế thừa từ một lớp đối tượng hỗ trợ một phần interface chúng cần và thực hiện composition đối với những đối tượng hỗ trợ phần interface còn lại.

Ý nghĩa

Nguyên lý Phân tách interface có mối liên hệ với nguyên lý Open-Closed và là một trong bốn nguyên lý cơ bản làm nền tảng cho phân tích thiết kế hướng đối tượng. Nó giúp giảm sự cồng kềnh, dư thừa không cần thiết cho phần mềm và quan trọng hơn là giảm sự kết dính (copuling) làm hạn chế tính linh động (flexibility) của phần mềm.

__________________
Trần Dũng - CIRENet
Posted by at No comments:

Wednesday, 26 June 2013


Bảng băm

CTDL: Bảng Băm

Các phép toán trên các cấu trúc dữ liệu như danh sách, cây nhị phân,… phần lớn được thực hiện bằng cách so sánh các phần tử của cấu trúc, do vậy thời gian truy xuất không nhanh và phụ thuộc vào kích thước của cấu trúc. Chương này Bảng băm sẽ giúp hạn chế số lần so sánh, và vì vậy sẽ cố gắng giảm thiểu được thời gian truy xuất. Độ phức tạp của các phép toán trên bảng băm thường có bậc là 0(1) và không phụ thuộc vào kích thước của bảng băm.
Những nội dung được giới thiệu gồm các chủ đề và các phép toán chính thường dùng trên cấu trúc bảng băm:
· Phép băm hay hàm băm (hash function)
· Tập khoá của các phần tử trên bảng băm
· Tập địa chỉ trên bảng băm
· Phép toán thêm phần tử vào bảng băm
· Phép toán xoá một phần tử trên bảng băm
· Phép toán tìm kiếm trên bảng băm
Thông thường bảng băm được sử dụng khi cần giải quyết những bài toán có các cấu trúc dữ liệu lớn và được lưu trữ ở bộ nhớ ngoài.
1. PHÉP BĂM (Hash Function)
1.1. Định nghĩa:
Trong hầu hết các ứng dụng, khoá được dùng như một phương thức để truy xuất dữ liệu một cách gián tiếp. Hàm được dùng để ánh xạ một khoá vào một dãy các số nguyên và dùng các giá trị nguyên này để truy xuất dữ liệu được gọi là hàm băm (hình 1)

Hình 1
Như vậy, hàm băm là hàm biến đổi khóa của phần tử thành địa chỉ trên bảng băm.
Khóa có thể là dạng số hay số dạng chuỗi. Giải quyết vấn đề băm với các khoá không phải là số nguyên:
  • Tìm cách biến đổi khoá thành số nguyên
    • Ví dụ loại bỏ dấu ‘-’ trong mã số 9635-8904 đưa về số nguyên 96358904
    • Đối với chuỗi, sử dụng giá trị các ký tự trong bảng mã ASCCI
  • Sau đó sử dụng các hàm băm chuẩn trên số nguyên.
1.2. Hàm Băm sử dụng Phương pháp chia
  • Dùng số dư:
    • h(k) = k mod m
    • k là khoá, m là kích thước của bảng.
  • Vấn đề chọn giá trị m
    • m = 2n (không tốt)
    • nếu chọn m= 2n thông thường không tốt  h(k) = k mod 2n sẽ chọn cùng n bits cuối của k
    • m là nguyên tố (tốt). Thông thường m được chọn là số nguyên tố gần với 2n. Chẳng hạn bảng ~4000 mục, chọn m = 4093
1.3. Hàm Băm sử dụng Phương pháp nhân
  • Sử dụng
    • h(k) = m (k A mod 1)
    • k là khóa, m là kích thước bảng, A là hằng số: 0 < A < 1
  • Chọn m và A
    • M thường chọn m = 2p
    • Sự tối ưu trong việc chọn A phụ thuộc vào đặc trưng của dữ liệu.
    • Theo Knuth chọn A = 1/2(Ö 5 -1) » 0.618033987 được xem là tốt.
1.4. Phép băm phổ quát
  • Việc chọn hàm băm m không tốt có thể dẫn đến xác suất đụng độ lớn.
  • Giải pháp:
    • Lựa chọn hàm băm h ngẫu nhiên.
    • Chọn hàm băm độc lập với khóa.
    • Khởi tạo một tập các hàm băm H phổ quát và từ đó h được chọn ngẫu nhiên.
    • Một tập các hàm băm H là phổ quát (universal ) nếu với mọi " f, k Î H và 2 khoá k, l ta có xác suất: Pr{f(k) = f(l)} <= 1/m
      • >
Ví dụ: Giả sử nếu khoá là một số nguyên, dương và HK(key) là một số nguyên với một digit từ 0..9, Thế thì, hàm băm sẽ dùng toán tử modulo-10 để trả về giá trị tương ứng của một khoá. Chẳng hạn: nếu khoá=49 thì HF(49)=9.
Một cách tổng quát, với một hàm băm, nhiều khoá khác nhau có thể cho cùng một giá trị băm. Trong tình huống này xảy ra sự xung đột (collision) và cần thiết phải giải quyết sự đụng độ này. Một trong những phương pháp giải quyết sự xung đột với thời gian nhanh là sử dụng các cấu trúc danh sách đặc, hay danh sách kề có kích thước cố định. (xem phần 4)
Các cấu trúc bảng băm đơn giản, thường được cài đặt bằng các danh sách kề. Do vậy, để truy xuất một phần tử trên các bảng băm thuộc loại này, chỉ cần hai khóa tương ứng với hàng thứ i và cột thứ j để định vị một phần tử trên bảng.
1.5. Bảng băm chữ nhật (m hàng, n cột):
Mỗi phần tử trên bảng chữ nhật tương ứng với hai khóa tương ứng hàng thứ i và cột thứ j, địa chỉ phần tử này trên danh sách kề được xác định qua hàm băm:
   0 ------------------->     j
0
 |
 |
 |
 |
V
i
0 1 2 ... n
1 x
2
...
...
m
Hình 1.2. Bảng băm chữ nhật
0 1 2 3 ... n-1 n n+1 n+2 ... m x n
Danh sách kề mô tả bảng băm hình chữ nhật
bảng băm: phần tử x thuộc hàng 2 cột 3 - f(1,2) = n + 3
Tổng quát, phần tử thuộc hàng i, cột j được cho bởi công thức:
f(i,j) =ni + j (n là số cột của bảng chữ nhật)
1.6. Bảng băm tam giác dưới (m hàng) và bảng băm tam giác trên (n cột):
Hình sau là bảng tam giác dưới m hàng

Hình 1.3.a Bảng băm tam giác dưới m hàng
Và bảng băm tam giác trên n cột

Hình 1.3.b Bảng băm tam giác trên n cột
Mỗi phần tử trên bảng tam giác dưới tương ứng với hai khóa hàng i, cột j(i>=j), địa chỉ phần tử này trên danh sách kề được xác định qua hàm băm:
f(i,j)=i(i+1)/2 + j
1.7. Bảng băm đường chéo (n cột):
Hình sau là các dạng bảng đường chéo n cột, hãy xác định hàm băm cho các bảng đường chéo này.
        
i = j
i = j hay i = j-1
i = j hay i = j+1
i = j hay i = j±1
Hình 1.4. Các bảng băm đường chéo
Như đã giới thiệu ở phần trên, với mỗi bảng băm đơn giản chúng ta cần xây dựng một hàm băm để truy xuất dữ liệu lưu trữ trong các phần tử trên bảng băm. Hàm băm thường có dạng công thức tổng quát HF(key) hay f(khoá) hoặc được tổ chức ở dạng bảng tra gọi là bảng truy xuất (access table).
2. BẢNG BĂM ADT (Hash Table - ADT)
Bảng băm ADT:
a. Mô tả dữ liệu
Giả sử
  • K: tập các khoá (set of keys)
  • M: tập các dịa chỉ (set of addresses).
  • HF(k): hàm băm dùng để ánh xạ một khoá k từ tập các khoá K thành một địa chỉ tương ứng trong tập M.
Tập khóa K                 Hàm băm                  Tập địa chỉ M
b. Các phép toán trên bảng băm
  • Khởi tạo (Initialize): Khởi tạo bảng băm, cấp phát vùng nhớ hay qui định số phần tử (kích thước) của bảng băm
  • Kiểm tra rỗng (Empty): kiểm tra bảng băm có rỗng hay không?
  • Lấy kích thước của bảng băm (Size): Cho biết số phần tử hiện có trong bảng băm
  • Tìm kiếm (Search): Tìm kiếm một phần tử trong bảng băm theo khoá k chỉ định trước.
  • Thêm mới phần tử (Insert): Thêm một phần tử vào bảng băm. Sau khi thêm số phần tử hiện có của bảng băm tăng thêm một đơn vị.
  • Loại bỏ (Remove): Loại bỏ một phần tử ra khỏi bảng băm, và số phần tử sẽ giảm đi một.
  • Sao chép (Copy): Tạo một bảng băm mới tử một bảng băm cũ đã có.
  • Duyệt (Traverse): duyệt bảng băm theo thứ tự địa chỉ từ nhỏ đến lớn.
Các Bảng băm thông dụng:

Với mỗi loại bảng băm cần thiết phải xác định tập khóa K, xác định tập địa chỉ M và xây dựng hàm băm HF cho phù hợp.
Mặt khác, khi xây dựng hàm băm cũng cần thiết phải tìm kiếm các giải pháp để giải quyết sự xung đột, nghĩa là giảm thiểu sự ánh xạ của nhiều khoá khác nhau vào cùng một địa chỉ (ánh xạ nhiều-một).
Bảng băm với phương pháp nối kết trực tiếp: mỗi địa chỉ của bảng băm(gọi là một bucket) tương ứng một danh sách liên kết.
Các phần tử bị xung đột được nối kết với nhau trên một danh sách liên kết.
Bảng băm với phương pháp nối kết hợp nhất: bảng băm loại này được cài đặt bằng danh sách kề, mỗi phần tử có hai trường: trường key chứa khóa của phần tử và trường next chỉ phần tử kế bị xung đột. Các phần tử bị xung đột được nối kết nhau qua trường nối kết next.
Bảng băm với phương pháp dò tuyến tính: ví dụ khi thêm phần tử vào bảng băm loại này nếu băm lần đầu bị xung đột thì lần lượt dò địa chỉ kế… cho đến khi gặp địa chỉ trống đầu tiên thì thêm phần tử vào địa chỉ này.
Bảng băm với phương pháp dò bậc hai: ví dụ khi thêm phần tử vào bảng băm loại này, nếu băm lần đầu bị xung đột thì lần lượt dò đến địa chi mới, lần dò i ở phần tử cách khoảng i2 cho đến khi gặp địa chỉ trống đầu tiên thì thêm phần tử vào địa chỉ này.
Bảng băm với phương pháp băm kép: bảng băm loại này dùng hai hàm băm khác nhau, băm lần đầu với hàm băm thứ nhất nếu bị xung đột thì xét địa chỉ khác bằng hàm băm thứ hai.
Ưu điểm của các Bảng băm:

Bảng băm là một cấu trúc dung hòa giữa thời gian truy xuất và dung lượng bộ nhớ:
- Nếu không có sự giới hạn về bộ nhớ thì chúng ta có thể xây dựng bảng băm với mỗi khóa ứng với một địa chỉ với mong muốn thời gian truy xuất tức thời.
- Nếu dung lượng bộ nhớ có giới hạn thì tổ chức một số khóa có cùng địa chỉ, lúc này thời gian truy xuất có bi suy giảm đôi chút.
Bảng băm dược ứng dụng nhiều trong thực tế, rất thích hợp khi tổ chức dữ liệu có kích thước lớn và được lưu trữ ở bộ nhớ ngoài.
3. VÍ DỤ VỀ CÁC HÀM BĂM
3.1. Hàm băm dạng bảng tra:
Hàm băm có thể tổ chức ở dạng bảng tra (còn gọi là bảng truy xuất), thông dụng nhất là ở dạng công thức.
Ví dụ sau đây là bảng tra với khóa là bộ chữ cái, bảng băm có 26 địa chỉ từ 0 đến 25. Khóa a ứng với địa chỉ 0, khoá b ứng với địa chỉ 1,… , z ứng với địa chỉ 25.
Khoá
Địa chỉ
Khóa
Địa chỉ
Khóa
Địa chỉ
Khóa
Địa chỉ
a
0
h
7
o
14
v
21
b
1
I
8
p
15
w
22
c
2
j
9
q
16
x
23
d
3
k
10
r
17
y
24
e
4
l
11
s
18
z
25
f
5
m
12
t
19
/
/
g
6
n
13
u
20
/
/
Hình 3.1 Hàm băm dạng bảng tra được tổ chức dưới dạng danh sách kề.
3.2. Hàm băm dạng công thức:
Thông thường hàm băm dạng công thức được xây dựng theo dạng tổng quát f(key).
Người ta thường dùng hàm băm chia dư (% modulo) như các ví dụ 1 và 2 sau:
Ví dụ 1: f(key) = key % 10:

Theo ví dụ này, hàm băm f(key) sẽ băm các số nguyên thành 10 địa chỉ khác nhau (ánh xạ vào các địa chỉ từ 0, 1,…, 9). Các khóa có hàng đơn vị là 0 được băm vào địa chỉ 0, các khóa có hàng đơn vị là i (i=0 | 1 | … | 9) được băm vào địa chỉ thứ i.
Ví dụ 2: f(key)=key % M:

Hàm băm loại này cho phép băm các số nguyên thành M địa chỉ khác nhau (ánh xạ vào các địa chỉ từ 0, 1,… M-1).
Ví dụ 3: 
Giả sử cần xây dựng một hàm băm với tập khóa số là chuổi 10 kí tự, tập địa chỉ có M địa chỉ khác nhau . Có nhiều cách để xây dựng hàm băm này, ví dụ cộng dồn mã ASCII của từng kí tự, sau đó chia dư (% modulo) cho M. Thông thường, hàm băm dạng công thức rất đa dạng và không bị ràng buộc bởi một tiêu chuẩn nào cả.
Yêu cầu đối với hàm băm tốt:
Một hàm băm tốt thường phải thỏa các yêu cầu sau:
  • Phải giảm thiểu sự xung đột.
  • Phải phân bố đều các phần tử trên M địa chỉ khác nhau của bảng băm.
4. CÁC CÁCH GIẢI QUYẾT XUNG ĐỘT
Như đã đề cập ở phần trên, sự xung đột là hiện tượng các khóa khác nhau nhưng băm cùng địa chỉ như nhau, hay ánh xạ vào cùng một địa chỉ
Một cách tổng quát, khi key1<>key2 mà f(key1)=f(key2) chúng ta nói phần tử có khóa key1 xung đột với phần tử có khóa key2.
Thực tế người ta giải quyết sự xung đột theo hai phương pháp: phương pháp nối kết và phương pháp băm lại.
Giải quyết sự xung đột bằng phương pháp nối kết:

Các phần tử bị băm cùng địa chỉ (các phần tử bị xung đột) được gom thành một danh sách liên kết. Lúc này mỗi phần tử trên bảng băm cần khai báo thêm trường liên kết next chỉ phần tử kế bị xung đột cùng địa chỉ.
Bảng băm giải quyết sự xung đột bằng phương pháp này cho phép tổ chức các phần tử trên bảng băm rất linh hoạt: khi thêm một phần tử vào bảng băm chúng ta sẽ thêm phần tử này vào danh sách liên kết thích hợp phụ thuộc vào băm. Tuy nhiên bảng bảng băm loại này bị hạn chế về tốc độ truy xuất.
Các loại bảng băm giải quyết sự xung đột bằng phương pháp nối kết như: bảng băm với phương pháp nối kết trực tiếp, bảng băm với phương pháp nối kết hợp nhất.
Giải quyết sự xung đột bằng phương pháp băm lại:

Nếu băm lần đầu bị xung đột thì băm lại lần 1, nếu bị xung đột nữa thì băm lai lần 2,… Quá trình băm lại diễn ra cho đến khi không còn xung đột nữa. Các phép băm lại (rehash function) thường sẽ chọn địa chỉ khác cho các phần tử.
Để tăng tốc độ truy xuất, các bảng băm giải quyết sự xung đột bằng phương pháp băm lại thường được cài đặt bằng danh sách kề. Tuy nhiên việc tổ chức các phần tử trên bảng băm không linh hoạt vì các phần tử chỉ được lưu trữ trên một danh sách kề có kích thước đã xác định trước.
Các loại bảng băm giải quyết sự xung đột bằng phương pháp băm lại như: bảng băm với phương pháp dò tuyến tính, bảng băm với phương pháp dò bậc hai, bảng băm với phương pháp băm kép.
4.1. Bảng băm với phương pháp nối kết trực tiếp (Direct chaining Method)
Mô tả: Xem hình vẽ

Hình 1.6. bảng băm với phương pháp nối kết trực tiếp
Bảng băm được cài đặt bằng các danh sách liên kết, các phần tử trên bảng băm được “băm” thành M danh sách liên kết (từ danh sách 0 đến danh sách M–1). Các phần tử bị xung đột tại địa chỉ i được nối kết trực tiếp với nhau qua danh sách liên kết i. Chẳng hạn, với M=10, các phần tử có hàng đơn vị là 9 sẽ được băm vào danh sách liên kết i = 9.
Khi thêm một phần tử có khóa k vào bảng băm, hàm băm f(k) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1 ứng với danh sách liên kết i mà phần tử này sẽ được thêm vào.
Khi tìm một phần tử có khóa k vào bảng băm, hàm băm f(k) cũng sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1 ứng với danh sách liên kết i có thể chứa phần tử này. Như vậy, việc tìm kiếm phần tử trên bảng băm sẽ được qui về bài toán tìm kiếm một phần tử trên danh sách liên kết.
Để minh họa cho vấn đề vừa nêu:
Xét bảng băm có cấu trúc như sau:
- Tập khóa K: tập số tự nhiên
- Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9}
- Hàm băm f(key) = key % 10.
Hình trên minh họa bảng băm vừa mô tả. Theo hình vẽ, bảng băm đã "băm" phần tử trong tập khoá K theo 10 danh sách liên kết khác nhau, mỗi danh sách liên kết gọi là một bucket:
· Bucket 0 gồm những phần tử có khóa tận cùng bằng 0.
· Bucket i(i=0 | … | 9) gồm những phần tử có khóa tận cùng bằng i. Để giúp việc truy xuất bảng băm dễ dàng, các phần tử trên các bucket cần thiết được tổ chức theo một thứ tự, chẳng hạn từ nhỏ đến lớn theo khóa.
· Khi khởi động bảng băm, con trỏ đầu của các bucket là NULL.
Theo cấu trúc này, với tác vụ insert, hàm băm sẽ được dùng để tính địa chỉ của khoá k của phần tử cần chèn, tức là xác định được bucket chứa phần tử và đặt phần tử cần chèn vào bucket này.
Với tác vụ search, hàm băm sẽ được dùng để tính địa chỉ và tìm phần tử trên bucket tương ứng.
Cài đặt bảng băm dùng phương pháp nối kết trực tiếp :

a. Khai báo cấu trúc bảng băm:

#define         M       100
typedef struct tagNODE
{
        int               key;
        tagNODE *next
}NODE, *NODEPTR;

/* khai bao mang bucket chua M con tro dau cua Mbucket */
NODEPTR bucket[M];
b.Các phép toán:
Hàm băm

Giả sử chúng ta chọn hàm băm dạng %: f(key)=key % M.
int hashfunc (int key)
{
return (key % M);
}
Chúng ta có thể dùng một hàm băm bất kì thay cho hàm băm dạng % trên.
Phép toán initbuckets:
Khởi động các bucket.
void initbuckets( )
{
for (int b=0;  b<M;  b++);
bucket[b] = NULL;
}
Phép toán emmptybucket:
Kiểm tra bucket b có bị rỗng không?
int emptybucket (int b)
{
return (bucket[b] ==NULL ?TRUE :FALSE);
}
Phép toán emmpty:
Kiểm tra bảng băm có rỗng không?
int empty( )
{

int b;
for (b = 0;b<M;b++)
if(bucket[b] !=NULL)  return(FALSE);
return(TRUE);
}
Phép toán insert:
Thêm phần tử có khóa k vào bảng băm.
Giả sử các phần tử trên các bucket là có thứ tự để thêm một phần tử khóa k vào bảng băm trước tiên chúng ta xác định bucket phù hợp, sau đó dùng phép toán place của danh sách liên kết để đặt phần tử vào vi trí phù hợp trên bucket.
void insert(int k)
{
int b;
b= hashfunc(k)
place(b,k); //tac vu place cua danh sach lien ket
}
Phép toán remove:
Xóa phần tử có khóa k trong bảng băm.
Giả sử các phần tử trên các bucket là có thứ tự, để xóa một phần tử khóa k trong bảng băm cần thực hiện:
- Xác định bucket phù hợp
- Tìm phần tử để xóa trong bucket đã được xác định, nếu tìm thấy phần tử cần xóa thì loại bỏ phần tử theo các phép toán tương tự loại bỏ một phần tử trong danh sách liên kết.
void remove ( int k)
{
int b;
NODEPTR q, p;
b = hashfunc(k);
p = hashbucket(k);
q=p;
while(p !=NULL && p->key !=k)
{
q=p;
p=p->next;
}
if (p == NULL)
printf("\n khong co nut co khoa %d" ,k);
else
if (p == bucket [b])   pop(b);
//Tac vu pop cua danh sach lien ket
else
delafter(q);
/*tac vu delafter cua danh sach lien ket*/
}
Phép toán clearbucket:
Xóa tất cả các phần tử trong bucket b.
void clearbucket (int b)
{
NODEPTR p,q;
//q la nut truoc,p la nut sau
q = NULL;
p = bucket[b];
while(p !=NULL)
{
q = p;
p=p->next;
freenode(q);
}
bucket[b] = NULL; //khoi dong lai butket b
}
Phép toán clear:
Xóa tất cả các phần tử trong bảng băm.
void clear( )
{
int b;
for (b = 0; b<M ; b++)
clearbucket(b);
}
Phép toán traversebucket:
Duyệt các phần tử trong bucket b.
void traversebucket (int b)
{
NODEPTR p;
p= bucket[b];
while (p !=NULL)
{
printf("%3d", p->key);
p= p->next;
}
}
Phép toán traverse:
Duyệt toàn bộ bảng băm.
void traverse( )
{
int b;
for (b = 0;n<M; b++)
{
printf("\nButket %d:",b);
traversebucket(b);
}
}
Phép toán search:
Tìm kiếm một phần tử trong bảng băm,nếu không tìm thấy hàm này trả về hàm NULL,nếu tìm thấy hàm này trả về con trả chỉ tìm phần tử tìm thấy.
NODEPTR search(int k)
{
NODEPTR p;
int b;
b = hashfunc (k);
p = bucket[b];
while(k > p->key && p !=NULL)
p=p->next;
if (p == NULL | | k !=p->key)// khong tim thay
return(NULL);
else//tim thay
// else //tim thay
return(p);
}
Nhận xét bảng băm dùng phương pháp nối kết trực tiếp :
Bảng băm dùng phương pháp nối kết trực tiếp sẽ "băm” n phần tử vào danh sách liên kết (M bucket).
Để tốc độ thực hiện các phép toán trên bảng hiệu quả thì cần chọn hàm băm sao cho băm đều n phần tử của bảng băm cho M bucket, lúc này trung bình mỗi bucket sẽ có n/M phần tử. Chẳng hạn, phép toán search sẽ thực hiện việc tìm kiếm tuyến tính trên bucket nên thời gian tìm kiếm lúc này có bậc 0 (n/M) – nghĩa là, nhanh gấp n lần so với việc tìm kiếm trên một danh sách liên kết có n phần tử.
Nếu chọn M càng lớn thì tốc độ thực hiện các phép toán trên bảng băm càng nhanh, tuy nhiên lại càng dùng nhiều bộ nhớ. Do vậy, cần điều chỉnh M để dung hòa giữa tốc độ truy xuất và dung lượng bộ nhớ.
· Nếu chọn M=n thì năng xuất tương đương với truy xất trên mảng (có bậc O(1)), tuy nhiên tốn nhiều bộ nhớ.
· Nếu chọn M =n /k(k =2,3,4,…) thì ít tốn bộ nhớ hơn k lần, nhưng tốc độ chậm đi k lần.
4.2. Bảng băm với phương pháp nối kết hợp nhất (Coalesced chaining Method)
Mô tả:

- Cấu trúc dữ liệu: Tương tự như trong trường hợp cài đặt bằng phương pháp nối kết trực tiếp, bảng băm trong trường hợp này được cài đặt bằng danh sách liên kết dùng mảng, có M phần tử. Các phần tử bị xung đột tại một địa chỉ được nối kết nhau qua một danh sách liên kết. Mỗi phần tử của bảng băm gồm hai trường:
· Trường key: chứa khóa của mỗi phần tử
· Trường next: con trỏ chỉ đến phần tử kế tiếp nếu có xung đột.
- Khởi động: Khi khởi động, tất cả trường key của các phần tử trong bảng băm được gán bởi giá trị Null, còn tất cả các trường next được gán –1.
- Thêm mới một phần tử: Khi thêm mới một phần tử có khóa key vào bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1.
· Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ này.
· Nếu bị xung đột thì phần tử mới được cấp phát là phần tử trống phía cuối mảng. Cập nhật liên kết next sao cho các phần tử bị xung đột hình thành một danh sách liên kết.
- Tìm kiếm: Khi tìm kiếm một phần tử có khóa key trong bảng băm, hàm băm f(key) sẽ giúp giới hạn phạm vi tìm kiếm bằng cách xác định địa chỉ i trong khoảng từ 0 đến M-1, và việc tìm kiếm phần tử khóa có khoá key trong danh sách liên kết sẽ xuất phát từ địa chỉ i.

Để minh họa cho bảng băm với phương pháp nối kết hợp nhất, xét ví dụ sau:
Giả sử, khảo sát bảng băm có cấu trúc như sau:
- Tập khóa K: tập số tự nhiên
- Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9}
- Hàm băm f(key) = key % 10.
Key : A C B D E
Hash: 1 2 1 1 3
key next
NULL -1
NULL -1
... ...
NULL -1
0 NULL -1
1 A M-1
2 C -1
3 E -1
... ...
M-2 D -1
M-1 B M-2
Cài đặt bảng băm dùng phương pháp nối kết hợp nhất:
a. Khai báo cấu trúc bảng băm:
#define NULLKEY –1
#define M 100
/* M la so nut co tren bang bam, du de chua cac nut nhap vao bang bam */
// Khai bao cau truc mot nut cua bang bam
struct node
{
int key; //khoa cua nut tren bang bam
int next;
//con tro chi nut ke tiep khi co xung dot
};

//Khai bao bang bam
struct node hashtable[M];
int avail;
/* bien toan cuc chi nut trong o cuoi table duoc cap nhat khi co xung dot */
b. Các tác vụ:
Hàm băm:
Giả sử chúng ta chọn hàm băm dạng modulo: f(key)=key % 10.
int hashfunc(int key)
{
return(key % 10);
}
Chúng ta có thể dùng một hàm băm bất kì thay cho hàm băm dạng % trên.
Phép toán khởi tạo (Initialize):
Phép toán này cho khởi động bảng băm: gán tất cả các phần tử trên bảng có trường key là Null, trường next là –1.
Gán biến toàn cục avail=M-1, là phần tử cuối danh sách chuẩn bị cấp phát néu xãy ra xung đột.
void initialize()
{
for(int i = 0;i<M;i++)
{
hashtable[i].key = NULLKEY;
hashtable[i].key = -1;
}
avail = M-1;
/* nut M-1 la nut o cuoi bang chuan bi cap phat neu co xung dot*/
}
Phép toán kiểm tra rỗng (empty):
Kiểm tra bảng băm có rỗng không.
int empty ();
{
int i;
for(i = 0;i< M;i++)
if(hashtable[i].key !=NULLKEY)
return(FALSE);
return(TRUE);
}
Phép toán tìm kiếm (search):
Tìm kiếm theo phương pháp tuyến tính, nếu không tìm thấy hàm tìm kiếm trả về trị M, nếu tìm thấy hàm này trả về địa chỉ tìm thấy.
int search(int k)
{
int i;
i=hashfunc(k);
while(k !=hashtable[i].key && i !=-1)
i=hashtable[i].next;
if(k== hashtable[i]key)
return(i);//tim thay
return(M);//khong tim thay
}
Phép toán lấy phần tử trống (Getempty):
Chọn phần tử còn trống phía cuối bản băm để cấp phát khi xảy ra xung đột.
int getempty()
{
while(hashtable[avail].key !=NULLKEY)  avail - -;
return(avail);
}
Phép toán chèn phần tử mới vào bảng băm (insert):
Thêm phần tử có khóa k vào bảng băm.
int insert(int k)
{
int i;
//con tro lan theo danh sach lien ket chua cac nut //bi xung dot
int j;
//dia chi nut trong duoc cap phat
i = search(k);
if(i !=M)
{
printf("\n khoa %d bi trung,khong them nut nay duoc",k);
return(i);
}
i=hashfunc(k);
while(hashtable[i]next >=0) i=hashtable[i].next;
if(hashtable[i].key == NULLKEY)
//Nut i con trong thi cap nhat
j = i;
else
//Neu nut i la nut cuoi cua DSLK
{
j = getempty();
if(j < 0)
{
printf("\n Bang bam bi day,khongthem nut co khoa %d duoc"k);
return(j);
}
else
hashtable[i].next = j;
}
hashtable[j].key = k;
return(j);
}
Nhận xét bảng băm dùng phương pháp nối kết hợp nhất:
Thực chất cấu trúc bảng băm này chỉ tối ưu khi băm đều, nghĩa là mỗi danh sách liên kết chứa một vài phần tử bị xung đột, tốc độ truy xuất lúc này có bậc 0(1). Trường hợp xấu nhất là băm không đều vì hình thành một danh sách có n phần tử nên tốc độ truy xuất lúc này có bậc 0(n).

Chương trình minh họa:

Chương trình Hashtable, dùng phương pháp nối kết hợp nhất (coalesced chaining method) - Cài đặt bằng danh sách kề.
             http://sites.google.com/site/ngo2uochung/courses/hashtable-coalescedchaining
4.3. Bảng băm với phương pháp dò tuyến tính (Linear Probing Method)
Mô tả:

- Cấu trúc dữ liệu: Bảng băm trong trường hợp này được cài đặt bằng danh sách kề có M phần tử, mỗi phần tử của bảng băm là một mẫu tin có một trường key để chứa khoá của phần tử.
Khi khởi động bảng băm thì tất cả trường key được gán Null
- Khi thêm phần tử có khoá key vào bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1:
· Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ này.
  • Nếu bị xung đột thì hàm băm lại lần 1, hàm f1 sẽ xét địa chỉ kế tiếp, nếu lại bị xung đột thì hàm băm thì hàm băm lại lần 2, hàm f2 sẽ xét địa chỉ kế tiếp nữa, …, và quá trình cứ thế cho đến khi nào tìm được địa chỉ trống và thêm phần tử mới vào địa chỉ này.
    •
    - Khi tìm một phần tử có khoá key trong bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1, tìm phần tử khoá key trong khối đặt chứa các phần tử xuất phát từ địa chỉ i.
    Hàm băm lại của phương pháp dò tuyến tính là truy xuất địa chỉ kế tiếp. Hàm băm lại lần i được biểu diễn bằng công thức sau:
    f(key)=(f(key)+i) %M với f(key) là hàm băm chính của bảng băm.
    Lưu ý địa chỉ dò tìm kế tiếp là địa chỉ 0 nếu đã dò đến cuối bảng.
    Giả sử, khảo sát bảng băm có cấu trúc như sau:
    - Tập khóa K: tập số tự nhiên
    - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9}
    - Hàm băm f(key) = key % 10.
    Hình thể hiện thêm các nut 32, 53, 22, 92, 17, 34, 24, 37, 56 vào bảng băm.
    0
    NULL
    0
    NULL
    0
    NULL
    0
    NULL
    0
    56
    1
    NULL
    1
    NULL
    1
    NULL
    1
    NULL
    1
    NULL
    2
    32
    2
    32
    2
    32
    2
    32
    2
    32
    3
    53
    3
    53
    3
    53
    3
    53
    3
    53
    4
    NULL
    4
    22
    4
    22
    4
    22
    4
    22
    5
    NULL
    5
    92
    5
    92
    5
    92
    5
    92
    6
    NULL
    6
    NULL
    6
    34
    6
    34
    6
    34
    7
    NULL
    7
    NULL
    7
    17
    7
    17
    7
    17
    8
    NULL
    8
    NULL
    8
    NULL
    8
    24
    8
    24
    9
    NULL
    9
    NULL
    9
    NULL
    9
    37
    9
    37
    Cài đặt bảng băm dùng phương pháp dò tuyến tính:
    a. Khai báo cấu trúc bảng băm:
    #define NULLKEY –1
    #define M 100
    /*
    M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam
    */
    //khai bao cau truc mot nnut cua bang bam
    struct node
    {
    int key; //khoa cua nut tren bang bam
    };

    //Khai bao bang bam co M nut
    struct node hashtable[M];
    int NODEPTR;
    /* bien toan cuc chi so nut hien co tren bang bam */

    b. Các tác vụ:
    Hàm băm:
    Giả sử chúng ta chọn hàm băm dạng%:f(key0=key %10.
    int hashfunc(int key)
    {
    return(key% 10);
    }
    Chúng ta có thể dùng một hàm băm bất kì thay cho hàm băm dạng % trên.
    Phép toán khởi tạo (initialize):
    Khởi tạo bảng băm.
    Gán tất cả các phần tử trên bảng có trường key là NULL.
    Gán biến toàn cục N=0.
    void initialize( )
    {
    int i;
    for(i=0;i<M;i++)
    hashtable[i].key=NULLKEY;
    N=0;
    //so nut hien co khoi dong bang 0
    }
    Phép toán kiểm tra trống (empty):
    Kiểm tra bảng băm có trống hay không.
    int empty( );
    {
    return(N==0 ? TRUE;FALSE);
    }
    Phép toán kiểm tra đầy (full):
    Kiểm tra bảng băm đã đầy chưa.
    int full( )
    {
    return (N==M-1 ? TRUE; FALSE);
    }
    Lưu ý bảng băm đầy khi N=M-1, chúng ta nên dành ít nhất một phần tử trống trên bảng băm.
    Phép toán search:
    Việc tìm kiếm phần tử có khoá k trên một khối đặc, bắt đầu từ một địa chỉ i = HF(k), nếu không tìm thấy phần tử có khoá k, hàm này sẽ trả về trị M, còn nếu tìm thấy, hàm này trả về địa chỉ tìm thấy.
    int search(int k)
    {
    int i;
    i=hashfunc(k);
    while(hashtable[i].key!=k && hashtable[i].key !=NULKEY)
    {
    //bam lai (theo phuong phap do tuyen tinh:fi(key)=f(key)+) % M
    i=i+1;
    if(i>=M)
    i=i-M;
    }
    if(hashtable[i].key==k) //tim thay
    return(i);
    else
    //khong tim thay
    return(M);
    }
    Phép toán insert:
    Thêm phần tử có khoá k vào bảng băm.
    int insert(int k)
    {
    int i, j;
    if(full( ))
    {
    printf("\n Bang bam bi day khong them nut co khoa %d duoc",k);
    return;
    }
    i=hashfunc(k);
    while(hashtable[i].key !=NULLKEY)
    {
    //Bam lai (theo phuong phap do tuyen tinh)
    i ++;
    if(i >M)  i= i-M;
    }
    hashtable[i].key=k;
    N=N+1;
    return(i);
    }
      Nhận xét bảng băm dùng phương pháp dò tuyến tính:
    Bảng băm này chỉ tối ưu khi băm đều, nghĩa là, trên bảng băm các khối đặc chứa vài phần tử và các khối phần tử chưa sử dụng xen kẻ nhau, tốc độ truy xuất lúc này có bậc 0(1). Trường hợp xấu nhất là băm không đều hoặc bảng băm đầy, lúc này hình thành một khối đặc có n phần tử, nên tốc độ truy xuất lúc này có bậc 0(n).
    Chương trình minh họa:

    Bảng băm, dùng phương pháp dò tuyến tính (linear proping method)-cài đặt bằng danh sách kề.
    http://sites.google.com/site/ngo2uochung/courses/hashtable-linearproping
    4.4. Bảng băm với phương pháp dò bậc hai (Quadratic Probing Method)
    Mô tả:
    - Cấu trúc dữ liệu: Bảng băm dùng phương pháp dò tuyến tính bị hạn chế do rải các phần tử không đều, bảng băm với phương pháp dò bậc hai rải các phần tử đều hơn.
    Bảng băm trong trường hợp này được cài đặt bằng danh sách kề có M phần tử, mỗi phần tử của bảng băm là một mẫu tin có một trường key để chứa khóa các phần tử.
    - Khi khởi động bảng băm thì tất cả trường key bị gán NULL.
    Khi thêm phần tử có khóa key vào bảng băm, hàm băm f(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1.
    · Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ i này.
    · Nếu bị xung đột thì hàm băm lại lần 1 f1 sẽ xác định địa chỉ cách 12, nếu lại bị xung đột thì hàm băm lại lần 2 f2 sẽ xét địa chỉ cách i 22 ,… , quá trình cứ thế cho đến khi nào tìm được trống và thêm phần tử vào địa chỉ này.
    - Khi tìm kiếm một phần tử có khóa key trong bảng băm thì xét phần tử tại địa chỉ i=f(key), nếu chưa tìm thấy thì xét phần tử cách i 12, 22, …, quá trình cứ thế cho đến khi tìm được khóa (trường hợp tìm thấy) hoặc rơi vào địa chỉ trống (trường hợp không tìm thấy).
    - Hàm băm lại của phương pháp dò bậc hai là truy xuất các địa chỉ cách bậc 2. Hàm băm lại hàm i được biểu diễn bằng công thức sau:
    fi(key)=( f(key) + i2 ) % M
    với f(key) là hàm băm chính của bảng băm.
    Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng.
    Bảng băm với phương pháp do bậc hai nên chọn số địa chỉ M là số nguyên tố.
    Bảng băm minh họa có cấu trúc như sau:
    - Tập khóa K: tập số tự nhiên
    - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9}
    - Hàm băm f(key) = key % 10.
    Cài đặt bảng băm dùng phương pháp dò bậc hai:
    a. Khai báo cấu trúc bảng băm:


    #define NULLKEY –1
    #define M 101
    /*
    M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam,chon M la so nguyen to
    */
    //Khai bao nut cua bang bam
    struct node
    {
    int key; //Khoa cua nut tren bang bam
    };
    //Khai bao bang bam co M nut
    struct node hashtable[M];
    int N;
    //Bien toan cuc chi so nut hien co tren bang bam

    b. Các tác vụ :
    Hàm băm:
    Giả sử chúng ta chọn hàm băm dạng%: f(key)=key %10.
    int hashfunc(int key)
    {
    return(key% 10);
    }
    Chúng ta có thể dùng một hàm băm bất kì tahy cho hàm băm dạng % trên.
    Phép toán initialize
    Khởi động hàm băm.
    Gán tất cả các phần tử trên bảng có trường key là NULLKEY.
    Gán biến toàn cục N=0.
    void initialize()
    {
    int i;
    for(i=0; i<M;i++)  hashtable[i].key = NULLKEY;
    N=0; //so nut hien co khoi dong bang 0
    }
    Phép toán empty:
    Kiểm tra bảng băm có rỗng không
    int empty()
    {
    return(N ==0 ?TRUE :FALSE);
    }
    Phép toán full:
    Kiểm tra bảng băm đã đầy chưa .
    int full()
    {
    return(N = = M-1 ?TRUE :FALSE);
    }
    Lưu ý bảng băm đầy khi N=M-1 chúng ta nên chừa ít nhất một phần tử trong trên bảng băm!
    Phép toán search:
    Tìm phần tử có khóa k trên bảng băm,nếu không tìm thấy hàm này trả về trị M, nếu tìm thấy hàm này trả về địa chỉ tìm thấy.
    int search(int k)
    {
    int i, d;
    i = hashfuns(k);
    d = 1;
    while(hashtable[i].key!=k&&hashtable[i].key !=NULLKEY)
    {
    //Bam lai (theo phuong phap bac hai)
    i = (i+d) % M;
    d = d+2;
    }
    hashtable[i].key =k;
    N = N+1;
    return(i);
    }
    Nhận xét bảng băm dùng phương pháp dò bậc hai:
    Nên chọn số địa chỉ M là số nguyên tố. Khi khởi động bảng băm thì tất cả M trường key được gán NULL, biến toàn cục N được gán 0.
    Bảng băm đầy khi N = M-1, và nên dành ít nhất một phần tử trống trên bảng băm.
    Bảng băm này tối ưu hơn bảng băm dùng phương pháp dò tuyến tính do rải rác phần tử đều hơn, nếu bảng băm chưa đầy thì tốc độ truy xuất có bậc 0(1). Trường hợp xấu nhất là bảng băm đầy vì lúc đó tốc độ truy xuất chậm do phải thực hiện nhiều lần so sánh.
     2.4.5. Bảng băm với phương pháp băm kép (Double hashing Method)
    Mô tả:
    - Cấu trúc dữ liệu: Bảng băm này dùng hai hàm băm khác nhau với mục đích để rải rác đều các phần tử trên bảng băm.
    Chúng ta có thể dùng hai hàm băm bất kì, ví dụ chọn hai hàm băm như sau:
    f1(key)= key %M.
    f2(key) =(M-2)-key %(M-2).
    bảng băm trong trường hợp này được cài đặt bằng danh sách kề có M phần tử, mỗi phần tử của bảng băm là một mẫu tin có một trường key để lưu khoá các phần tử.
    - Khi khởi động bảng băm,tất cả trường kay được gán NULL.
    - Khi thêm phần tử có khoá key vào bảng băm, thì i=f1(key) và j=f2(key) sẽ xác định địa chỉ i và j trong khoảng từ 0 đến M-1:
    · Nếu chưa bị xung đột thì thêm phần tử mới tại địa chỉ i này.
    · Nếu bị xung đột thì hàm băm lại lần 1 f1 sẽ xét địa chỉ mới i+j, nếu lại bị xung đột thì hàm băm lại lần 2 f2 sẽ xét địa chỉ i+2j, …, quá trình cứ thế cho đến khi nào tìm được địa chỉ trống và thêm phần tử vào địa chi này.
    - Khi tìm kiếm một phần tử có khoá key trong bảng băm, hàm băm i=f1(key) và j=f2(key) sẽ xác định địa chỉ i và j trong khoảng từ 0 đến M-1. Xét phần tử tại địa chỉ i, nếu chưa tìm thấy thì xét tiếp phần tử i+ji+2j, …, quá trình cứ thế cho đến khi nào tìm được khoá (trường hợp tìm thấy) hoặc bị rơi vào địa chỉ trống (trường hợp không tìm thấy).
    Bảng băm dùng hai hàm băm khác nhau, hàm băm lại của phương pháp băm kép được tính theo I (từ hàm băm thứ nhất) và j (từ hàm băm thứ hai) theo một công thức bất kì, ở đây minh họa bằng địa chỉ mới cách j. Nếu đã dò đến cuối bảng thì trở về dò lại từ đầu bảng.
    Bảng băm với phương pháp băm kép nên chọn số địa chỉ M là số nguyên tố.
    Bảng băm minh họa có cấu trúc như sau:
    - Tập khóa K: tập số tự nhiên
    - Tập địa chỉ M: gồm 10 địa chỉ (M={0, 1, …, 9}
    - Hàm băm f(key) = key % 10.
    Minh hoạ:
    Sau đây là minh hoạ cho bảng băm có tập khóa là tạâp số tự nhiên,tập địa chỉ có 11 địa chỉ (M=11)(từ địa chỉ 0 đến 10),chọn hàm băm f1(key)=key % 10 và f2(key)=9-key %9.
    Xem việc minh hoạ này như một bài tập.
    Cài đặt bảng băm dùng phương pháp băm kép:
    a. Khai báo cấu trúc bảng băm:

    #define NULLKEY –1
    #define M 101
    /*M la so nut co tren bang bam,du de chua cac nut nhap vao bang bam,chon M la so nguyen to
    */
    //Khai bao phan tu cua bang bam
    struct node
    {
    int key;//khoa cua nut tren bang bam
    };

    //khai bao bang bam co M nut
    struct node hashtable[M];
    int N;
    //bien toan cuc chi so nut hien co tren bang bam

    b. Các tác vụ:
    Hàm băm:
    Giả sử chúng ta chọn hai hàm băm dạng %:
    f1(key0=key %M va f2(key) =M-2-key%(M-2).
    //Ham bam thu nhat
    int hashfunc(int key)
    {
    return(key%M);
    }
    //Ham bam thu hai
    int hashfunc2(int key)
    {
    return(M-2 – key%(M-2));
    }
    Chúng ta có thể dùng hai hàm băm bất kỳ thay cho hai hàm băm dạng % trên.
    Phép toán initialize :
    Khởi động bảng băm.
    Gán tất cả các phần tử trên bảng có trường key là NULL.
    Gán biến toàn cục N = 0.
    void initialize()
    {
    int i;
    for (i = 0 ; i<M ; i++ )
    hashtable [i].key = NULLKEY;
    N = 0;// so nut hien co khoi dong bang 0
    }
    Phép toán empty :
    Kiểm tra bảng băm có rỗng không.
    int empty() .
    {
    return (N == 0 ? TRUE : FALSE) ;
    }
    Phép toán full :
    Kiểm tra bảng băm đã đầy chưa.
    int full() .
    {
    return (N == M-1 ? TRUE : FALSE) ;
    }
    Lưu ý bảng băm đầy khi N=M-1, chúng ta nên dành ít nhất một phần tử trống trên bảng băm.
    Phép toán search :
    Tìm kiếm phần tử có khóa k trên bảng băm, nếu không tìm thấy hàm này trả về về trị M, nếu tìm thấy hàm này trả về địa chỉ tìm thấy.
    int search(int k)
    {
    int i, j ;
    i = hashfunc (k);
    j = hashfunc2 (k);
    While (hashtable [i].key!=k && hashtable [i] .key ! = NULLKEY)
    //bam lai (theo phuong phap bam kep)
    i = (i+j) % M ;
    if (hashtable [i]).key == k) // tim thay
    return (i) ;
    else// khong tim thay
    return (M) ;
    }
    Phép toán insert :
    Thêm phần tử có khoá k vào bảng băm.
    int insert(int k)
    {
    int i, j;
    if (full () )
    {
    printf ("Bang bam bi day") ;
    return (M) ;
    }
    if (search (k) < M)
    {
    printf ("Da co khoa nay trong bang bam") ;
    return (M) ;
    }
    i = hashfunc (k) ;
    j = hashfunc 2 (k) ;
    while (hashtable [i].key ! = NULLEY)
    // Bam lai (theo phuong phap bam kep)
    i = (i + j) % M;
    hashtable [i].key = k ;
    N = N+1;
    return (i) ;
    }
    Nhận xét bảng băm dùng phương pháp băm kép:

    Nên chọn số địa chỉ M là số nguyên tố.
    Bảng băm đầy khi N = M-1, chúng ta nên dành ít nhất một phần tử trống trên bảng băm.
    Bảng băm được cài đặt theo cấu trúc này linh hoạt hơn bảng băm dùng phương pháp dò tuyến tính và bảng băm dùng phương pháp sò bậc hai, do dùng hai hàm băm khác nhau nên việc rải phần tử mang tính ngẫu nhiên hơn, nếu bảng băm chưa đầy tốc độ truy xuất có bậc O(1). Trường hợp xấu nhất là bảng băm gần đầy, tốc độ truy xuất chậm do thực hiện nhiều lần so sánh.
    5. TỔNG KẾT VỀ PHÉP BĂM
  • Bảng băm đặt cơ sở trên mảng.
  • Phạm vi các giá trị khóa thường lớn hơn kích thước của mảng.
  • Một giá trị khóa được băm thành một chỉ mục của mảng bằng hàm băm.
  • Việc băm một khóa vào vào một ô đã có dữ liệu trong mảng gọi là sự đụng độ.
  • Sự đụng độ có thể được giải quyết bằng hai phương pháp chính: Phương pháp nối kết và phương pháp băm lại.
  • Trong phương pháp băm lại, các mục dữ liệu được băm vào các ô đã có dữ liệu sẽ được đưa vào ô khác trong mảng.
  • Trong phương pháp nối kết, mỗi phần tử trong mảng có một danh sách liên kết. Các mục dữ liệu được băm vào các ô sẽ được đưa vào danh sách ở ô đó.
    • Vấn đề Hàm băm

  • Hàm băm dùng phương pháp chia: h(k) = k mod m
  • m là kích thước bảng băm, k là khóa.
  • Hàm băm dùng phương pháp nhân: h(k) = ë m(k A mod 1)û
  • Knuth đề nghị A = 0.6180339887

    • Số lần đụng đô: (ví dụ)
     Kích thước bảng băm
     PP chia
     PP Nhân
     200
    698
     699
     512
     470
     466
     997
     309
     288
     1024
     301
     292

  • Theo bảng trên kết quả cho thấy kích thước bảng băm tỷ lệ nghịch với số lần đụng độ. Số đụng độ còn phụ thuộc vào phương pháp sử dụng hàm băm. · Hệ số tải là tỉ số giữa các mục dữ liệu trong một bảng băm với kích thước của mảng.
  • Hệ số tải cực đại trong phương pháp băm lại khoảng 0,5. Đối với băm kép ở Hệ số tải này (0,5), các phép tìm kiếm sẽ có chiều dài thăm dò trung bình là 2.
  • Trong phương pháp băm lại , thời gian tìm kiếm sẽ là vô cực khi hệ số tải đạt đến 1.
  • Điều quan trọng trong phương pháp băm lại là bảng băm không bao giờ được quá đầy.
  • Phương pháp nối kết thích hợp với hệ số tải là 1.
  • Với hệ số tải này, chiều dài thăm dò trung bình là 1,5 khi phép tìm thành công, và là 2.0 khi phép tìm thất bại.
  • Chiều dài thăm dò trong phương pháp nối kết tăng tuyến tính theo hệ số tải.
  • Kích thước của bảng băm thường là số nguyên tố. Điều này đặc biệt quan trọng trong thăm dò bậc hai và trong phương pháp nối kết.
  • Các bảng băm có thể dùng cách lưu trữ ngoại. Một cách để thực hiện việc này là cho các phần tử trong bảng băm chứa số lượng các khối của tập tin trên đĩa
    •  
    :https://sites.google.com/site/ngo2uochung/courses/ctdl-hashtable


    Posted by at No comments:
    Subscribe to: Posts (Atom)