Android AsyncTask & Android IPC

Using AsyncTask:

AsyncTask allows you to perform asynchronous work on your user interface. It performs the blocking operations in a worker thread and then publishes the results on the UI thread, without requiring you to handle threads and/or handlers yourself.

To use it, you must subclass AsyncTask and implement the doInBackground() callback method, which runs in a pool of background threads. To update your UI, you should implement onPostExecute(), which delivers the result from doInBackground() and runs in the UI thread, so you can safely update your UI. You can then run the task by calling execute() from the UI thread.

For example, you can implement the previous example using AsyncTask this way:

public void onClick(View v) {
    new DownloadImageTask().execute("http://example.com/image.png");
}

private class DownloadImageTask extends AsyncTask {
    /** The system calls this to perform work in a worker thread and
      * delivers it the parameters given to AsyncTask.execute() */
    protected Bitmap doInBackground(String... urls) {
        return loadImageFromNetwork(urls[0]);
    }
    
    /** The system calls this to perform work in the UI thread and delivers
      * the result from doInBackground() */
    protected void onPostExecute(Bitmap result) {
        mImageView.setImageBitmap(result);
    }
}

Now the UI is safe and the code is simpler, because it separates the work into the part that should be done on a worker thread and the part that should be done on the UI thread.

You should read the AsyncTask reference for a full understanding on how to use this class, but here is a quick overview of how it works:

- You can specify the type of the parameters, the progress values, and the final value of the task, using generics
- The method doInBackground() executes automatically on a worker thread
- onPreExecute(), onPostExecute(), and onProgressUpdate() are all invoked on the UI thread
- The value returned by doInBackground() is sent to onPostExecute()
- You can call publishProgress() at anytime in doInBackground() to execute onProgressUpdate() on the UI thread
- You can cancel the task at any time, from any thread. This is imporatnat for example if you want to provide a user to stop button which essentially stops an asynchronous task call in worker thread

Caution: Another problem you might encounter when using a worker thread is unexpected restarts in your activity due to a runtime configuration change (such as when the user changes the screen orientation), which may destroy your worker thread. To see how you can persist your task during one of these restarts and how to properly cancel the task when the activity is destroyed, see the source code for the Shelves sample application.

Thread-safe methods:

In some situations, the methods you implement might be called from more than one thread, and therefore must be written to be thread-safe.

This is primarily true for methods that can be called remotely—such as methods in a bound service. When a call on a method implemented in an IBinder originates in the same process in which the IBinder is running, the method is executed in the caller's thread. However, when the call originates in another process, the method is executed in a thread chosen from a pool of threads that the system maintains in the same process as the IBinder (it's not executed in the UI thread of the process). For example, whereas a service's onBind() method would be called from the UI thread of the service's process, methods implemented in the object that onBind() returns (for example, a subclass that implements RPC methods) would be called from threads in the pool. Because a service can have more than one client, more than one pool thread can engage the same IBinder method at the same time. IBinder methods must, therefore, be implemented to be thread-safe.

Similarly, a content provider can receive data requests that originate in other processes. Although the ContentResolver and ContentProvider classes hide the details of how the interprocess communication is managed, ContentProvider methods that respond to those requests—the methods query(), insert(), delete(), update(), and getType()—are called from a pool of threads in the content provider's process, not the UI thread for the process. Because these methods might be called from any number of threads at the same time, they too must be implemented to be thread-safe.

Interprocess Communication:

Android offers a mechanism for interprocess communication (IPC) using remote procedure calls (RPCs), in which a method is called by an activity or other application component, but executed remotely (in another process), with any result returned back to the caller. This entails decomposing a method call and its data to a level the operating system can understand, transmitting it from the local process and address space to the remote process and address space, then reassembling and reenacting the call there. Return values are then transmitted in the opposite direction. Android provides all the code to perform these IPC transactions, so you can focus on defining and implementing the RPC programming interface.

To perform IPC, your application must bind to a service, using bindService(). For more information, see the Services developer guide.

Processes & Threads in Android

Processes and Threads:

When an application component starts and the application does not have any other components running, the Android system starts a new Linux process for the application with a single thread of execution. By default, all components of the same application run in the same process and thread (called the "main" thread). If an application component starts and there already exists a process for that application (because another component from the application exists), then the component is started within that process and uses the same thread of execution. However, you can arrange for different components in your application to run in separate processes, and you can create additional threads for any process.

This document discusses how processes and threads work in an Android application.

Every application runs in its own process and all components of the application run in that process, by default.
Any slow, blocking operations in an activity should be done in a new thread, to avoid slowing down the user interface.

Processes:

By default, all components of the same application run in the same process and most applications should not change this. However, if you find that you need to control which process a certain component belongs to, you can do so in the manifest file.

The manifest entry for each type of component element—, , , and —supports an android:process attribute that can specify a process in which that component should run. You can set this attribute so that each component runs in its own process or so that some components share a process while others do not. You can also set android:process so that components of different applications run in the same process—provided that the applications share the same Linux user ID and are signed with the same certificates.

The element also supports an android:process attribute, to set a default value that applies to all components.

Android might decide to shut down a process at some point, when memory is low and required by other processes that are more immediately serving the user. Application components running in the process that's killed are consequently destroyed. A process is started again for those components when there's again work for them to do.

When deciding which processes to kill, the Android system weighs their relative importance to the user. For example, it more readily shuts down a process hosting activities that are no longer visible on screen, compared to a process hosting visible activities. The decision whether to terminate a process, therefore, depends on the state of the components running in that process. The rules used to decide which processes to terminate is discussed below.

Process lifecycle:

The Android system tries to maintain an application process for as long as possible, but eventually needs to remove old processes to reclaim memory for new or more important processes. To determine which processes to keep and which to kill, the system places each process into an "importance hierarchy" based on the components running in the process and the state of those components. Processes with the lowest importance are eliminated first, then those with the next lowest importance, and so on, as necessary to recover system resources.

There are five levels in the importance hierarchy. The following list presents the different types of processes in order of importance (the first process is most important and is killed last):

Foreground process

A process that is required for what the user is currently doing. A process is considered to be in the foreground if any of the following conditions are true:

It hosts an Activity that the user is interacting with (the Activity's onResume() method has been called).
It hosts a Service that's bound to the activity that the user is interacting with.
It hosts a Service that's running "in the foreground"—the service has called startForeground().
It hosts a Service that's executing one of its lifecycle callbacks (onCreate(), onStart(), or onDestroy()).
It hosts a BroadcastReceiver that's executing its onReceive() method.
Generally, only a few foreground processes exist at any given time. They are killed only as a last resort—if memory is so low that they cannot all continue to run. Generally, at that point, the device has reached a memory paging state, so killing some foreground processes is required to keep the user interface responsive.

Visible process

A process that doesn't have any foreground components, but still can affect what the user sees on screen. A process is considered to be visible if either of the following conditions are true:
It hosts an Activity that is not in the foreground, but is still visible to the user (its onPause() method has been called). This might occur, for example, if the foreground activity started a dialog, which allows the previous activity to be seen behind it.
It hosts a Service that's bound to a visible (or foreground) activity.
A visible process is considered extremely important and will not be killed unless doing so is required to keep all foreground processes running.

Service process

A process that is running a service that has been started with the startService() method and does not fall into either of the two higher categories. Although service processes are not directly tied to anything the user sees, they are generally doing things that the user cares about (such as playing music in the background or downloading data on the network), so the system keeps them running unless there's not enough memory to retain them along with all foreground and visible processes.

Background process

A process holding an activity that's not currently visible to the user (the activity's onStop() method has been called). These processes have no direct impact on the user experience, and the system can kill them at any time to reclaim memory for a foreground, visible, or service process. Usually there are many background processes running, so they are kept in an LRU (least recently used) list to ensure that the process with the activity that was most recently seen by the user is the last to be killed. If an activity implements its lifecycle methods correctly, and saves its current state, killing its process will not have a visible effect on the user experience, because when the user navigates back to the activity, the activity restores all of its visible state. See the Activities document for information about saving and restoring state.

Empty process

A process that doesn't hold any active application components. The only reason to keep this kind of process alive is for caching purposes, to improve startup time the next time a component needs to run in it. The system often kills these processes in order to balance overall system resources between process caches and the underlying kernel caches.
Android ranks a process at the highest level it can, based upon the importance of the components currently active in the process. For example, if a process hosts a service and a visible activity, the process is ranked as a visible process, not a service process.

In addition, a process's ranking might be increased because other processes are dependent on it—a process that is serving another process can never be ranked lower than the process it is serving. For example, if a content provider in process A is serving a client in process B, or if a service in process A is bound to a component in process B, process A is always considered at least as important as process B.

Because a process running a service is ranked higher than a process with background activities, an activity that initiates a long-running operation might do well to start a service for that operation, rather than simply create a worker thread—particularly if the operation will likely outlast the activity. For example, an activity that's uploading a picture to a web site should start a service to perform the upload so that the upload can continue in the background even if the user leaves the activity. Using a service guarantees that the operation will have at least "service process" priority, regardless of what happens to the activity. This is the same reason that broadcast receivers should employ services rather than simply put time-consuming operations in a thread.

Threads

When an application is launched, the system creates a thread of execution for the application, called "main." This thread is very important because it is in charge of dispatching events to the appropriate user interface widgets, including drawing events. It is also the thread in which your application interacts with components from the Android UI toolkit (components from the android.widget and android.view packages). As such, the main thread is also sometimes called the UI thread.

The system does not create a separate thread for each instance of a component. All components that run in the same process are instantiated in the UI thread, and system calls to each component are dispatched from that thread. Consequently, methods that respond to system callbacks (such as onKeyDown() to report user actions or a lifecycle callback method) always run in the UI thread of the process.

For instance, when the user touches a button on the screen, your app's UI thread dispatches the touch event to the widget, which in turn sets its pressed state and posts an invalidate request to the event queue. The UI thread dequeues the request and notifies the widget that it should redraw itself.

When your app performs intensive work in response to user interaction, this single thread model can yield poor performance unless you implement your application properly. Specifically, if everything is happening in the UI thread, performing long operations such as network access or database queries will block the whole UI. When the thread is blocked, no events can be dispatched, including drawing events. From the user's perspective, the application appears to hang. Even worse, if the UI thread is blocked for more than a few seconds (about 5 seconds currently) the user is presented with the infamous "application not responding" (ANR) dialog. The user might then decide to quit your application and uninstall it if they are unhappy.

Additionally, the Andoid UI toolkit is not thread-safe. So, you must not manipulate your UI from a worker thread—you must do all manipulation to your user interface from the UI thread. Thus, there are simply two rules to Android's single thread model:

- Do not block the UI thread
- Do not access the Android UI toolkit from outside the UI thread

Worker threads

Because of the single thread model described above, it's vital to the responsiveness of your application's UI that you do not block the UI thread. If you have operations to perform that are not instantaneous, you should make sure to do them in separate threads ("background" or "worker" threads).

For example, below is some code for a click listener that downloads an image from a separate thread and displays it in an ImageView:

public void onClick(View v) {
    new Thread(new Runnable() {
        public void run() {
            Bitmap b = loadImageFromNetwork("http://example.com/image.png");
            mImageView.setImageBitmap(b);
        }
    }).start();
}

At first, this seems to work fine, because it creates a new thread to handle the network operation. However, it violates the second rule of the single-threaded model: do not access the Android UI toolkit from outside the UI thread—this sample modifies the ImageView from the worker thread instead of the UI thread. This can result in undefined and unexpected behavior, which can be difficult and time-consuming to track down.

To fix this problem, Android offers several ways to access the UI thread from other threads. Here is a list of methods that can help:

- Activity.runOnUiThread(Runnable)
- View.post(Runnable)
- View.postDelayed(Runnable, long)

For example, you can fix the above code by using the View.post(Runnable) method:

public void onClick(View v) {
    new Thread(new Runnable() {
        public void run() {
            final Bitmap bitmap = loadImageFromNetwork("http://example.com/image.png");
            mImageView.post(new Runnable() {
                public void run() {
                    mImageView.setImageBitmap(bitmap);
                }
            });
        }
    }).start();
}

Now this implementation is thread-safe: the network operation is done from a separate thread while the ImageView is manipulated from the UI thread.

However, as the complexity of the operation grows, this kind of code can get complicated and difficult to maintain. To handle more complex interactions with a worker thread, you might consider using a Handler in your worker thread, to process messages delivered from the UI thread. Perhaps the best solution, though, is to extend the AsyncTask class, which simplifies the execution of worker thread tasks that need to interact with the UI.

Concepts related to threads & processes.

Concepts:

Multithreading:

Multithreading as a widespread programming and execution model allows multiple threads to exist within the context of a single process. These threads share the process's resources but are able to execute independently. The threaded programming model provides developers with a useful abstraction of concurrent execution. However, perhaps the most interesting application of the technology is when it is applied to a single process to enable parallel execution on a multiprocessor system.

This advantage of a multithreaded program allows it to operate faster on computer systems that have multiple CPUs, CPUs with multiple cores, or across a cluster of machines — because the threads of the program naturally lend themselves to truly concurrent execution. In such a case, the programmer needs to be careful to avoid race conditions, and other non-intuitive behaviors. In order for data to be correctly manipulated, threads will often need to rendezvous in time in order to process the data in the correct order. Threads may also require mutually-exclusive operations (often implemented using semaphores) in order to prevent common data from being simultaneously modified, or read while in the process of being modified. Careless use of such primitives can lead to deadlocks.

Another use of multithreading, applicable even for single-CPU systems, is the ability for an application to remain responsive to input. In a single-threaded program, if the main execution thread blocks on a long-running task, the entire application can appear to freeze. By moving such long-running tasks to a worker thread that runs concurrently with the main execution thread, it is possible for the application to remain responsive to user input while executing tasks in the background. On the other hand, in most cases multithreading is not the only way to keep a program responsive, with non-blocking I/O and/or Unix signals being available for gaining similar results

Race conditions arise in software when separate processes or threads of execution depend on some shared state. Operations upon shared states are critical sections that must be mutually exclusive in order to avoid harmful collision between processes or threads that share those states.

Address space: Address space is seperate for process but threads of a process share the same addresss space.
Data sharing(bteween threads & processes): Self Read.
Communication: Communication between processes are through signals.

Memory protection is an issue when you are in the same address space. How do you encounter it? Through memory protection register.
Memory protection is a way to control memory access rights on a computer, and is a part of most modern operating systems. The main purpose of memory protection is to prevent a process from accessing memory that has not been allocated to it. This prevents a bug within a process from affecting other processes, or the operating system itself. Memory protection for computer security includes additional techniques such as address space layout randomization and executable space protection.

Thread Safe/Thread Safety:

In computer programming, thread-safe describes a program portion or routine that can be called from multiple programming threads without unwanted interaction between the threads. (A thread is an instance of the program running on behalf of some user or process.) Thread safety is of particular importance to Java programmers, since Java is a programming language that provides built-in support for threads. By using thread-safe routines, the risk that one thread will interfere and modify data elements of another thread is eliminated by circumventing potential data race situations with coordinated access to shared data.

It is possible to ensure that a routine is thread-safe by:

Making sure that concurrent threads use synchronized algorithms that cooperate with each other.
Confining the address of a shared object to one thread whenever an unsynchronized algorithm is active..

Thread safety is a computer programming concept applicable in the context of multi-threaded programs. A piece of code is thread-safe if it only manipulates shared data structures in a manner that guarantees safe execution by multiple threads at the same time. There are various strategies for making thread-safe data structures. Thread safety is a property that allows code to run in multi-threaded environments by re-establishing some of the correspondences between the actual flow of control and the text of the program, by means of synchronization.

Synchronization and thread safety in Java:

As soon as we start using concurrent threads, we need to think about various issues that fall under the broad description of thread safety. Generally, we need to take steps to make sure that different threads don't interact in negative ways:

if one thread is operating on some data or structure, we don't want another thread to simultaneously operate on that same data/structure and corrupt the results;
when Thread A writes to a variable that Thread B accesses, we need to make sure that Thread B will actually see the value written by Thread A;
we don't want one thread to hog, take or lock for too long a resource that other threads need in order to make progress.

Synchronisation:

In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or commit to a certain sequence of action. Data synchronization refers to the idea of keeping multiple copies of a dataset in coherence with one another, or to maintain data integrity. Process synchronization primitives are commonly used to implement data synchronization.

Thread or process synchronization:

Thread synchronization or serialization, strictly defined, is the application of particular mechanisms to ensure that two concurrently-executing threads or processes do not execute specific portions of a program at the same time. If one thread has begun to execute a serialized portion of the program, any other thread trying to execute this portion must wait until the first thread finishes. Synchronization is used to control access to state both in small-scale multiprocessing systems -- in multithreaded environments and multiprocessor computers -- and in distributed computers consisting of thousands of units -- in banking and database systems, in web servers, and so on.

InterThread Communication in Java

1. Reading 1
2. Reading 2
3. Reading 3

InterProcess Communication:

In computing, Inter-process communication (IPC) is a set of methods for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC methods are divided into methods for message passing, synchronization, shared memory, and remote procedure calls (RPC). The method of IPC used may vary based on the bandwidth and latency of communication between the threads, and the type of data being communicated.
There are several reasons for providing an environment that allows process cooperation:
Information sharing
Speedup
Modularity
Convenience
Privilege separation
IPC may also be referred to as inter-thread communication and inter-application communication.
The combination of IPC with the address space concept is the foundation for address space independence/isolation.

Main IPC methods

Method: Provided by (operating systems or other environments)

File: Most operating systems
Signal: Most operating systems; some systems, such as Windows, implement signals in only the C run-time library and provide no support for their use as an IPC method.
Socket: Most operating systems
Message queue: Most operating systems
Pipe: All POSIX systems, Windows
Named pipe: All POSIX systems, Windows
Semaphore: All POSIX systems, Windows
Shared memory: All POSIX systems, Windows
Message passing:
(shared nothing) Used in MPI paradigm, Java RMI, CORBA, MSMQ, MailSlots, others
Memory-mapped file: All POSIX systems, Windows; this method may carry race condition risk if a temporary file is used.

Threads, Processes & related concepts.

Threads & Processes(In terms of Java - Source(Oracle)):

Processes and Threads

In concurrent programming, there are two basic units of execution: processes and threads. In the Java programming language, concurrent programming is mostly concerned with threads. However, processes are also important.

A computer system normally has many active processes and threads. This is true even in systems that only have a single execution core, and thus only have one thread actually executing at any given moment. Processing time for a single core is shared among processes and threads through an OS feature called time slicing.

It's becoming more and more common for computer systems to have multiple processors or processors with multiple execution cores. This greatly enhances a system's capacity for concurrent execution of processes and threads — but concurrency is possible even on simple systems, without multiple processors or execution cores.

Processes

A process has a self-contained execution environment. A process generally has a complete, private set of basic run-time resources; in particular, each process has its own memory space.

Processes are often seen as synonymous with programs or applications. However, what the user sees as a single application may in fact be a set of cooperating processes. To facilitate communication between processes, most operating systems support Inter Process Communication (IPC) resources, such as pipes and sockets. IPC is used not just for communication between processes on the same system, but processes on different systems.

Most implementations of the Java virtual machine run as a single process. A Java application can create additional processes using a ProcessBuilder object. Multiprocess applications are beyond the scope of this lesson.

Threads

Threads are sometimes called lightweight processes. Both processes and threads provide an execution environment, but creating a new thread requires fewer resources than creating a new process.

Threads exist within a process — every process has at least one. Threads share the process's resources, including memory and open files. This makes for efficient, but potentially problematic, communication.

Multithreaded execution is an essential feature of the Java platform. Every application has at least one thread — or several, if you count "system" threads that do things like memory management and signal handling. But from the application programmer's point of view, you start with just one thread, called the main thread. This thread has the ability to create additional threads, as we'll demonstrate in the next section.

Thread Objects

Each thread is associated with an instance of the class Thread. There are two basic strategies for using Thread objects to create a concurrent application.

To directly control thread creation and management, simply instantiate Thread each time the application needs to initiate an asynchronous task.
To abstract thread management from the rest of your application, pass the application's tasks to an executor.

Threads & Processes (from different sources) -

Source 1:
Process:
Each process provides the resources needed to execute a program. A process has a virtual address space, executable code, open handles to system objects, a security context, a unique process identifier, environment variables, a priority class, minimum and maximum working set sizes, and at least one thread of execution. Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads.

Thread:
A thread is the entity within a process that can be scheduled for execution. All threads of a process share its virtual address space and system resources. In addition, each thread maintains exception handlers, a scheduling priority, thread local storage, a unique thread identifier, and a set of structures the system will use to save the thread context until it is scheduled. The thread context includes the thread's set of machine registers, the kernel stack, a thread environment block, and a user stack in the address space of the thread's process. Threads can also have their own security context, which can be used for impersonating clients.

Source 2:
Both processes and threads are independent sequences of execution. The typical difference is that threads (of the same process) run in a shared memory space, while processes run in separate memory spaces. Threads are an operating environment feature, rather than a CPU feature (though the CPU typically has operations that make threads efficient).

Source 3:
Process:
An executing instance of a program is called a process.
Some operating systems use the term ‘task‘ to refer to a program that is being executed.
A process is always stored in the main memory also termed as the primary memory or random access memory.
Therefore, a process is termed as an active entity. It disappears if the machine is rebooted.
Several process may be associated with a same program.
On a multiprocessor system, multiple processes can be executed in parallel.
On a uni-processor system, though true parallelism is not achieved, a process scheduling algorithm is applied and the processor is scheduled to execute each process one at a time yielding an illusion of concurrency.
Example: Executing multiple instances of the ‘Calculator’ program. Each of the instances are termed as a process.

Thread:
A thread is a subset of the process.
It is termed as a ‘lightweight process’, since it is similar to a real process but executes within the context of a process and shares the same resources allotted to the process by the kernel (See kquest.co.cc/2010/03/operating-system for more info on the term ‘kernel’).
Usually, a process has only one thread of control – one set of machine instructions executing at a time.
A process may also be made up of multiple threads of execution that execute instructions concurrently.
Multiple threads of control can exploit the true parallelism possible on multiprocessor systems.
On a uni-processor system, a thread scheduling algorithm is applied and the processor is scheduled to run each thread one at a time.
All the threads running within a process share the same address space, file descriptor, stack and other process related attributes.
Since the threads of a process share the same memory, synchronizing the access to the shared data withing the process gains unprecedented importance.

Source 4:
In computer science, a thread of execution is the smallest unit of processing that can be scheduled by an operating system. The implementation of threads and processes differs from one operating system to another, but in most cases, a thread is contained inside a process. Multiple threads can exist within the same process and share resources such as memory, while different processes do not share these resources. In particular, the threads of a process share the latter's instructions (its code) and its context (the values that its variables reference at any given moment). To give an analogy, multiple threads in a process are like multiple cooks reading off the same cook book and following its instructions, not necessarily from the same page.

On a single processor, multithreading generally occurs by time-division multiplexing (as in multitasking): the processor switches between different threads. This context switching generally happens frequently enough that the user perceives the threads or tasks as running at the same time. On a multiprocessor or multi-core system, the threads or tasks will actually run at the same time, with each processor or core running a particular thread or task.
Many modern operating systems directly support both time-sliced and multiprocessor threading with a process scheduler. The kernel of an operating system allows programmers to manipulate threads via the system call interface. Some implementations are called a kernel thread, whereas a lightweight process (LWP) is a specific type of kernel thread that shares the same state and information.

Programs can have user-space threads when threading with timers, signals, or other methods to interrupt their own execution, performing a sort of ad-hoc time-slicing.


Differences between Threads & Processes:

Threads differ from traditional multitasking operating system processes in that:
processes are typically independent, while threads exist as subsets of a process
processes carry considerably more state information than threads, whereas multiple threads within a process share process state as well as memory and other resources
processes have separate address spaces, whereas threads share their address space
processes interact only through system-provided inter-process communication mechanisms
Context switching between threads in the same process is typically faster than context switching between processes.
Systems like Windows NT and OS/2 are said to have "cheap" threads and "expensive" processes; in other operating systems there is not so great a difference except the cost of address space switch which implies a TLB flush.

Other major difference between threads and processes is:

Threads share the address space of the process that created it; processes have their own address space.
Threads have direct access to the data segment of its process; processes have their own copy of the data segment of the parent process.
Threads can directly communicate with other threads of its process; processes must use interprocess communication to communicate with sibling processes.
Threads have almost no overhead; processes have considerable overhead.
New threads are easily created; new processes require duplication of the parent process.
Threads can exercise considerable control over threads of the same process; processes can only exercise control over child processes.
Changes to the main thread (cancellation, priority change, etc.) may affect the behavior of the other threads of the process; changes to the parent process does not affect child processes.

More differences Between Threads and Processes:

Threads share the address space of the process that created it; processes have their own address. Threads have direct access to the data segment of its process; processes have their own copy of the data segment of the parent process. Threads can directly communicate with other threads of its process; processes must use inter-process communication to communicate with sibling processes. Threads have almost no overhead; processes have considerable overhead. New threads are easily created; new processes require duplication of the parent process. Threads can exercise considerable control over threads of the same process; processes can only exercise control over child processes.

Changes to the main thread (cancellation, priority change, etc.) may affect the behavior of the other threads of the process, changes to the parent process does not affect child processes.

Both have an id, set of registers, state, priority, and scheduling policy.
Both have attributes that describe the entity to the OS.
Both have an information block.
Both share resources with the parent process.
Both function as independent entities from the parent process.
The creator can exercise some control over the thread or process.
Both can change their attributes.
Both can create new resources.
Neither can access the resources of another process.

Other sources:

An application consists of one or more processes. A process, in the simplest terms, is an executing program. One or more threads run in the context of the process. A thread is the basic unit to which the operating system allocates processor time. A thread can execute any part of the process code, including parts currently being executed by another thread.

A process is a collection of code, memory, data and other resources. A thread is a sequence of code that is executed within the scope of the process. You can (usually) have multiple threads executing concurrently within the same process.

A single process can have multiple threads that share global data and address space with other threads running in the same process, and therefore can operate on the same data set easily. Processes do not share address space and a different mechanism must be used if they are to share data.
If we consider running a word processing program to be a process, then the auto-save and spell check features that occur in the background are different threads of that process which are all operating on the same data set (your document).

Process:
In computing, a process is an instance of a computer program that is being sequentially executed. It contains the program code and its current activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently.

A computer program is a passive collection of instructions; a process is the actual execution of those instructions. Several processes may be associated with the same program; for example, opening up several instances of the same program often means more than one process is being executed. Multitasking is a method to allow multiple processes to share processors (CPUs) and other system resources. Each CPU executes a single task at a time. However, multitasking allows each processor to switch between tasks that are being executed without having to wait for each task to finish. Depending on the operating system implementation, switches could be performed when tasks perform input/output operations, when a task indicates that it can be switched, or on hardware interrupts.

A common form of multitasking is time-sharing. Time-sharing is a method to allow fast response for interactive user applications. In time-sharing systems, context switches are performed rapidly. This makes it seem like multiple processes are being executed simultaneously on the same processor. The execution of multiple processes seemingly simultaneously is called concurrency. For security and reliability reasons most modern operating systems prevent direct communication between independent processes, providing strictly mediated and controlled inter-process communication functionality.

Thread:
A single process may contain several executable programs (threads) that work together as a coherent whole. One thread might, for example, handle error signals, another might send a message about the error to the user, while a third thread is executing the actual task of the...

Link: Another good read.

Specifying how to sort data in Java: Comparators

Specifying how to sort data in Java: Comparators

If you've seen the previous posts you'll know that -

So far, we've seen how to sort data and that Java is "naturally" sortable, i.e. implements the Comparable interface, or else make our own data implement Comparable so that it can be sorted. But of course this model has limitations:

if the class in question doesn't already implement Comparable– or doesn't implement it in the way you want– and you can't subclass it, then implementing Comparable isn't an option;
a single Comparable implementation is awkward if you want different sorting modes for the same class.
Java gets round these limitations with another interface, Comparator. A Comparator implementation provides a method specifying how any two objects of a given class are to be ordered. To specify how a collection of objects is to be sorted, Java then provides various places where we can "plug in" a Comparator of our choosing.

Below, we dive in and look at an example Comparator for sorting Strings by length.

Comparator example: sorting Strings by length

We introduced the notion of a Comparator in Java, which is used to specify the sort order of a particular class. Let's start with an example to sort Strings by their length. We thus want to write a Comparator that compares Strings. So the general format of our Comparator will be as follows:

public class StringLengthComparator implements Comparator {
  public int compare(String o1, String o2) {
    return ...
  }
}

Now, we just need to make the compare() return method return an appropriate value to indicate the ordering. Effectively, the logic of this method should be o1.compareTo(o2). That is– as discussed when we reviewed sorting_comparable_compareto(in previous post) the compareTo() method– it should return:

a negative number if (and only if) o1 comes before o2;
a positive number if (and only if) o1 comes after o2;
else 0.
So a simple implementation would be1:

public class StringLengthComparator implements Comparator {
  public int compare(String o1, String o2) {
    if (o1.length() < o2.length()) {
      return -1;
    } else if (o1.length() > o2.length()) {
      return 1;
    } else {
      return 0;
    }
  }
}

Now, armed with our Comparator and some vital string data that we need ordering by length:

String[] strs = {"boxer shorts", "grundies", "boxers",
  "elasticated Y-fronts", "underpants", "briefs"};

we can sort our string data by length with a simple call to Arrays.sort(), this time passing in an instance of our parameter:

// Sort
Arrays.sort(strs, new StringLengthComparator());
// Print the results
for (String s : strs)
  System.out.println(s);

And lo and behold, our garments are sorted in correct lengthwise order:

boxers
briefs
grundies
underpants
boxer shorts
elasticated Y-fronts

Note that, as discussed on the Java sort algorithm, the sort is stable. That is, strings with the same length are guaranteed not to be reversed, and so our boxers correctly precede our briefs.

Note 1: 1. Some programmers prefer the more succinct version return o1.length() < o2.length() ? -1 : (o1.length() > o2.length() ? 1 : 0);. It is also presumably safe to use a subtraction– on 32-bit architecture at least, it's impossible to have Java Strings long enough to overflow when doing the subtraction! (from: Javamex.com)

Making your Java objects sortable

Making your Java objects sortable: the Comparable interface

In the last post, we looked at how to sort 'naturally' sortable objects in Java such as Strings and Integers. But supposing we've created our own class to represent some arbitrary object or data and want to sort instances of that class? Well, Java can still sort a list of our objects, providing that we tell Java how to order any two instances. For this, we need implement the Comparable interface.

Implementing Comparable

Let's consider an example of a class that represents a playing card in a normal deck of cards. For simplicity, the card will have a suit and a number, both represented by an integer. (In more sophisticated implementations, you might consider using Enums instead of an integers.) When we order our cards, we firstly want them ordered according to suit. We'll define a particular order, namely alphabetical order according to suit name, which in English would be clubs, diamonds, hearts, spades1. Then within a suit, we want the cards ordered numerically.

public class PlayingCard {
  public static final int SUIT_CLUBS    = 1;
  public static final int SUIT_DIAMONDS = 2;
  public static final int SUIT_HEARTS   = 3;
  public static final int SUIT_SPADES   = 4;
  ...

  private int suit;
  private int number;
}

We start by making our class implement the Comparable interface. How exactly this looks depends on whether you're using Java 5 or later (in other words, whether your version of Java supports generics). The generic version looks like this:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    ...
  }
}

whereas the non-generic (pre Java 5) verion looks like this:

public class PlayingCard implements Comparable {
  public int compareTo(Object o) {
    ...
  }
}

In the non-generic version, we'll have some extra casting to do, but the logic will be essentially the same. We need to make the compareTo() method return an integer that determines the order of two playing cards (this playing card with respect to the one passed in). Now, we look in more detail at implementing the compareTo() method.

Making your Java objects sortable: the compareTo method

We just saw that to make our objects sortable, we need to make them implement the Comparable interface. This means providing a compareTo() method that will define the order of two instances of a given object. Specifically, our compareTo() method needs to return an integer as follows:

a negative number if our object comes before the one passed in;
a positive number if our object comes after the one passed in;
otherwise, zero (meaning they're equal in terms of ordering).
Note that the magnitude of the number doesn't matter. The aim isn't to say "how different" the two objects are, just in which direction. So often, we may as well use -1 and 1 to mean "before" and "after" respectively.

In our example of playing cards, we want to order first by suit and then by number. So we first consider what number we would return just by comparing the suit. If this number is not zero, then we can just return that number: if the suit's different, we don't need to bother comparing the number. So the first part of our comparison looks as follows:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    if (this.suit < o.suit) {
      return -1;
    } else if (this.suit > o.suit) {
      return 1;
    } else {
      // compare number
    }
  }
}

Now we're left with the cases of cards with an identical suit, in which case we need to compare the number in a similar manner:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    if (this.suit < o.suit) {
      return -1;
    } else if (this.suit > o.suit) {
      return 1;
    } else {
      // suit is identical: compare number
      if (this.number < o.number) {
        return -1;
      } else if (this.number > o.number) {
        return 1;
      } else {
        return 0;
      }
    }
  }
}

Optimising the compareTo() method

The above implementation of compareTo() will work fine. It has the advantage of being easy to follow. If you write the method this way, you're unlikely to run into trouble.

The method as it stands has the slight disadvantage that it's not very succinct and involves a lot of comparisons. In certain circumstances we can reduce the number of comparisons. On the next page, we'll look at possible optimisations to the compareTo() method. We'll also see that care needs to be taken when applying such optimisations.

Optimising the compareTo method...

We saw an example implementation of the compareTo() method of the Comparable interface. Our implementation was methodical and easy to follow, but a bit "long-winded".

...so long as we're careful!

In some cases we can make the comparison method more succinct, but we need to proceed with caution as we'll see in a second.

Using a subtraction instead of a comparison

The first optimisation that can be made in certain cases is to use a subtraction instead of a comparison of numeric values. In principle, this works thanks to some extremely elementary mathematics:

if a < b, then a - b will be negative; if a > b, then a - b will be positive.
Oh, and of course subtracting a number from itself gives zero. So our card comparison routine can now look as follows:

public class PlayingCard implements Comparable {
  public int compareTo(PlayingCard o) {
    int cardComp = this.suit - o.suit;
    if (cardComp == 0) {
      cardComp = this.number - o.number;
    }
    return cardComp;
  }
}

Using subtraction is a very common idiom for comparing numbers in sorting routines, and is almost certainly the reason why compareTo() is defined to return an integer in the first place. Indeed, you may be wondering why we bothered with the previous version of doing comparisons and returning specific values. Well, it turns out that the subtraction method is incorrect for the general case, although it works here.

Problem with this method: comparing large numbers

The above method works because we know that the numbers we'll be comparing will be small. But ints can only store numbers up to a certain magnitude. So if we know that the difference between the two numbers can exceed about 2 billion (232) we should avoid the above method. Converting to longs gives us extra breathing space (the magnitude can now read 263), but the essential problem remains.

This means, for example, that if you're comparing database keys, you should check very carefully what your database's key allocation policy is if you intend to use this method. (Just because you only have 100,000 keys in your table may not mean that the keys are allocated from that range of numbers.)

Is it worth it?

In tests If you run(on Intel architecture), you will see that:

when the compareTo() involves a single comparison, using a subtraction instead of comparisons makes no appreciable difference;
when two comparisons are involved, using subtraction as above (so that our method has just a single comparison with zero) makes the overall sort about 10% faster.
In other words, in the single-variable case, the "optimisation" appears non-existent and in the two-variable case, the performance benefits are minimal. Possibly the main benefit is therefore a readability issue, at least on modern architecture.

Next...

Next, you may wish to look at how to set an arbitrary sort order using the Java Comparator interface.

Sorting Data with Java Collections

Sorting data with Java Collections: introduction

Here, we will look at how to sort data in Java. To start off with, we'll assume that the problem we have is the following:

we have a List or array of Java objects that is (possibly) out of order;
we want to sort this list or array as a "one-off" action.

By "one-off", we mean that we don't need to keep the list permanently in order as we add and remove elements, though Java does also provide 'permanently sorted' structures if that is what we require. But generally, sorting a list or array can be broken down into two problems:

given any two of the objects that you want to sort (e.g. two Strings if you're sorting a list of string data), how do you determine the correct order of the two elements?;
given the ability to determine the order of two elements, how do you construct a sorting algorithm to sort an entire list of data?
Strictly speaking, these problems aren't totally separate, because some algorithms rely on us being able to measure how far apart two items are. But for sorting in Java, we can generally see the problem in the above two stages. And in fact, for most practical purposes:

Java already provides a good enough solution to the second problem;
for many objects that have an obvious "natural ordering" (e.g. Integers, Floats, Strings), Java also provides a solution to the first problem.
In other words, for the simplest case of sorting a list of Strings or Integers (among other 'simple' objects), Java provides a one-line solution.

Where to go next...

We will look at:

how to sort a list of Strings and other "simple" objects in Java;
how to let Java sort arbitrary objects of your own class, by implementing the Comparable interface;
how to specify your own sort order (whether the objects in question are 'naturally' sortable or not) using Java's Comparator interface.

How to sort a list(a simple object type) of Strings or Integers in Java -

Following on from our introduction to sorting in Java, we consider here one of the simplest cases of sorting a List of simple objects such as Strings or Integers. Let's say we have a simple list of Strings:

List words = new ArrayList(50);
words.add("once");
words.add("upon");
words.add("a");
words.add("time");
...

Now, we can sort this list with a simple call to the following library method:

Collections.sort(words);

The Collections.sort() method will work "out of the can" on lists of various "basic" objects that you'd expect to be able to sort, including instances of Number– the primitive wrapper classes Integer, Long, Float etc plus BigInteger and BigDecimal.

Sorting an array

Sorting an array of these objects is just as easy(Refer point 1 as well at bottom of this post):

Arrays.sort(myArray);

The above method takes an array of objects, but the Arrays class also provides similar methods for sorting primitive arrays.

Next: other issues

What we've seen above is that sorting simple objects in Java such as numbers or strings is generally dead simple. But there are a couple more issues to deal with on the following pages:

What if we want to sort a different type of object, such as one that we've created? For this, we need to look at how to use the Java Comparable interface.
What if we want to control the ordering of a specific type of sort, even if the objects in question are 'naturally sortable'? For example, we might want to perform a case insensitive sort on Strings, or perform a "proper" alphabetic sort that takes account of things like the correct ordering of accents in non-English strings. For this, we need to look at Java Comparators.
In some cases, we may need to consider the performance of the Java sort algorithm: in particular, where we are repeatedly sorting very small lists, a simpler (even if less scalable) algorithm may work better.

Note:

1. In fact, the Collections.sort() method copies the list into an array and calls the Arrays.sort() method before copying the elements back into the list.

Performance of the Java Sorting algorithm -

1. Reading 1
2. Reading 2

Making decision for picking right Java Collection

How to choose which Java collection class to use?

The Java Collections API provides a whole host of data structures, especially since the API was expanded in Java 5 (and again slightly in Java 6) to include concurrent collections. At first, the array of choices can be a little daunting: should I use a HashMap or a LinkedHashMap? When should I use a list or a HashSet? When should I use a TreeMap rather than a HashMap? But with a bit of guidance, the choice needn't be quite so daunting. There are also a few cases where it's difficult to decide because the choice is very arguable. And in other cases, having a clear set of rules of thumb can guide you to an appropriate decision.

Basic approach to choosing a collection

The overall approach I'd suggest for choosing is as follows:

choose the general type of organisation that your data needs to have (e.g. map or list); without too much thought, this is usually fairly clear;
then, choose the implementation of that type that has the minimum functionality that you actually require (e.g. don't choose a sorted structure if you don't actually need the data to be sorted).
In general, the algorithm that underlies each collection class is designed to be a good tradeoff between efficiency and certain minimal requirements. So as long as you understand the minimal requirements that a given class is designed to provide, you shouldn't need to get too bogged down in the actual algorithms (though if you are interested in algorithms, the source code to all the collections classes is available and they make fascinating case studies, of course).

The following table/links here(Javamex.com) gives you further insight into details of making right decision -

1. Reading 1
2. Reading 2

Overriding hashcode() & equals()

Making your class compatible with Java hash maps: overriding hashCode() and equals()

If you've read the previous post's hash function guidelines from Javamex, or if you have prior knowledge of hashing, then you may have an idea of how to write the hash function itself. On this page we'll discuss the nuts and bolts you need to actually plug your hash function into a Java class and therefore use instances of that class as a hash map key. (Note that we concentrate on HashMaps here, but the points we discuss generally hold for related classes such as ConcurrentHashMap and HashSet.)

The basics: override hashCode() and equals()

Put very simply, there are two methods that a class needs to override to make objects of that class work as hash map keys:

public int hashCode();
public boolean equals(Object o);

As you might expect, the hashCode() method is where we put our hash function. Hash functions such as those mentioned in our hash function guidelines can generally be slotted in. Note that HashMap will not do any extra caching of the hash code. So if calculating the hash is relatively expensive (as in the case of String) it may be worth explicitly caching the hash code.

The equals() method

The equals() method must return true if the fields of the current object equal those of the object passed in, else return false. By "equal", we generally mean that primitive fields match via the == operator, and objects are either both null or both non-null and match via the equals() method. Note two important constraints on equals():

if x.equals(y) returns true, then the hash codes of x and y must be identical;
it must be reflexive and transitive: that is, x.equals(y) must return the same value as y.equals(x), and if x.equals(y) and y.equals(z), then x.equals(z) must also be true (see below for what this actually means in real terms!).
The first of these is generally common sense given that the purpose of a hash function is to "narrow down a search" which will ultimately be performed using the equals() to perform the final check for a match. The second is more or less common sense, but it does mean, for example, that we can't allow a null reference to equal an "empty" object. It also means, strictly speaking, that a subclass cannot add new variable comparisons to the equals() method(Refer point 2 at bottom).

Example

Now let's see an example. We'll look at a simple class that encapsulates a pair of screen coordinates. We assume that individually, the X and Y coordinates are essentially random, but that the maximum coordinate in each case will be in the order of a couple of thousand (in other words will have about 10 or 11 bits of randomness). So to make the hash code, we pick a number that is roughly halfway between these bits, then find a prime (or at worst odd) number that is close to 211. Our old favourite of 31 (=25-1) will do us fine. The equals() method is trivial, but note the convention of returning false if the object passed in isn't of a compatible type.

public class CoordinatePair {
  private int x, y;
  public int hashCode() {
    return (x * 31) ^ y;
  }
  public boolean equals(Object o) {
    if (o instanceof CoordinatePair) {
      CoordinatePair other = (CoordinatePair) o;
      return (x == other.x && y == other.y);
    }
    return false;
  }
}

In words of Javamex.com -

1. This convention predates Java 5 generics: arguably, we really don't expect a case where equals() will be called against an object of an incompatible type and should just apply the case an rely on the resulting runtime exception if the cast fails.

2. The problem with subclassing can be explained with a quick example. Suppose we extend Rectangle (whose equals() method effectively compares its co-ordinates and dimensions, although via the Rectangle2D base class) to make a class called ColouredRectangle, whose equals() method returns true if and only if the colours of the rectangles are identical. Now we have the problem that a plain Rectangle, if passed a ColouredRectangle to its equals() method, would return true provided the co-ordinates and dimensions were the same, discounting the colour; whereas the other way round, ColouredRectangle.equals() would always return false (because it wasn't comparing against another ColouredRectangle).

Hashing (Java)

Hashing, a technique used (among other applications) to implement Java's common map and set classes. Hashing is designed to solve the problem of needing to efficiently find or store an item in a collection. For example, if we have a list of 10,000 words of English and we want to check if a given word is in the list, it would be inefficient to successively compare the word with all 10,000 items until we find a match. Hashing is a technique to make things more efficient by effectively narrowing down the search at the outset.

What is hashing?

Hashing means using some function or algorithm to map object data to some representative integer value. This so-called hash code (or simply hash) can then be used as a way to narrow down our search when looking for the item in the map.

Hashing's concept is explained from very basic to detailed steps over here - Javamex.com

Readings for Hashing -

1. Reading 1 (Basic understanding)
2. Reading 2 (Java HashMaps)
3. Reading 3 (Further down in Hashing & HashMaps)
4. Reading 4 (Improving Hash function)
5. Reading 5 (String Hash function as implemented in Java)
6. Reading 6 (Digging in binary Implementations)
7. Reading 7 (String Hash function technical details)
8. Reading 8 (String Hash function technical details 2)
9. Reading 9 (Writing a hash function in Java, implementing hashcode)
10. Reading 10 (Hash Code advanced)

Maps (Java Collections)

Using collections in Java: Maps

In programming terms, a map is a set of associations between pairs of objects. It crops up extremely frequently in programming in all sorts of cases where we want to deal with cases of "for X, what is the Y"? For example:

"for a given language code, what is the message to display meaning 'Please log in'?"
"for a given word in the document I'm processing, how many times did it occur do far?"
"for a given row ID number, what is the cached copy of the row from the database"?
"for a given user on my web server, what is their current session status"?
Notice the third item here: a common use for a map is as a simple cache.

Creating and using a map

The syntax for creating a map is largely similar to lists and sets. But this time we need to specify the type of object we want to map from and the type to map to. Let's say we want to store an association of country codes with country names, in other words, String to String:

Map countryNames = new HashMap(200);

In this case, we use the common map implementation HashMap. As with the set, we supply an estimate of the number of mappings we expect to add, to help the map operate more efficiently1. To add an association to the map, we actually use a method called put():

countryNames.put("GB", "Great Britain");
countryNames.put("FR", "France");
countryNames.put("IT", "Italy");
countryNames.put("FW", "Far Far Away");

Then, to retrieve the country name for a particular code, we call:

String name = countryNames.get("IT");

Other things to note about Maps:

The items that we associate from are called keys; the items they are associated to (the country names here) are called values.
If for a particular key there is no associated value, then get() returns null.
A given key can be associated with only one value. If you put("X", "Y") then subsequently put("X", "Z"), then get("X") will return Z, the last association made with that key.
The put() method actually returns the previous association with the given key (or null if there was none).

More on maps

For more advanced uses, it is useful to understand how maps work, in particular about the technique called hashing from which the HashMap and HashSet get their name.

Note: Every time a collection becomes "full", it generally has to re-organise itself to accommodate the extra capacity needed. For example, an ArrayList needs to create a new, larger array. In the case of HashSet or HashMap, it turns out that this re-organisation is quite an "expensive" operation. So if we can anticipate roughly how many items will be added in the first place, we cut down on this expensive re-organisation.

How Maps work

The map is a fundamental type of structure that allows associations to be set up between one set of objects and another. By association, we typically mean situations where we want to say "for a given X, what is the Y?". For example:

for a given IP address, what is the host name?
for a given request to our web server, what is the last result we returned?
for a given parameter, what is the corresponding value?
for a given session ID, what is the user name?
In other words, maps have a wide variety of uses. Various routines would be inefficient and fiddly to write without them. Generally we can see that a map, or an instance of the Java Map interface, is a set of associations. So for example, we could have a map of string parameters to integer values:

Map params = ...

Then, we can set and get parameters on this map:

params.set("maxConnections", 20);
params.set("maxThreads", 10);
...
int maxConnections = params.get("maxConnections");
int maxThreads = params.get("maxThreads");

The items that we associate from are referred to as keys. The items that we associate to (the integers in this case) are, in Java at least, usually referred to simply as values. Conceptually, you could imagine (and in principle implement) a Map as an array containing the keys and another array containing the values, with code such as the following to get an item out of the map:

public Integer get(String key) {
  for (int i = 0; i < keys.length; i++) {
    if (key.equals(keys[i])) {
      return values[i];
    }
  }
  return null;
}

Note that instances of Map always map objects to objects. So in fact, a Map of strings to integers would store Integer objects as the values. In our above example, we can (so long as we're careful about nulls) read and write straight to int primitives thanks to the 'autoboxing' feature of Java 5.

Introducing the hash map

Now, implementing a map with two arrays like this is conceptually simple, but would actually be quite inefficient for maps of any significant size. For example, imagine if the map had 10,000 entries in it (and in practical uses, it's not uncommon to want to store tens of thousands of items if not more in a map). In that case, on average we'd have to compare 5,000 items with the one passed in every time we called get()! One improvement that may be appropriate in some cases is to store the list sorted (and actually, Java provides some map implementations based on keeping the map data sorted, albeit in a more sophisticated way than a simple list). But that in turn can make insertions and deletions from the map expensive, since on every operation we have to maintain the map in its sorted state.

An alternative to keeping the map data sorted is to use hashing.

Sets (Java Collections)

Using collections in Java: Sets

Sets are used to test whether an item is "present or not" in the collection, but without allowing duplicates and generally without keeping items in a fixed order, unlike lists.

A List such as an ArrayList is useful in cases where we want to store some arbitrary large group of objects in a fixed order, and possibly refer to those objects by their position in the list. But a list is not so good for another type of problem where:

we don't necessarily care about ordering;
we don't care about the number of times that an object is in the collection;
we just want to know if a given object is in the collection or not.
A collection in which an object may be "present or not" (but not present multiple times) is called a set.

Why use a set?

It may have occurred to you that you could use a plain old list for the above purpose. After all, List has a contains() method to see if a given object is in the list, and to preserve the present-or-not condition, we could just check before adding if the given object was already in the list, and if so not add it again. So what's the point of a "set"?

The point is simply efficiency:

If your only necessary criterion is present or not and you don't need the extra functionality of a list (such as ordering, being able to retrieve the nth item), then it is possible to use a more efficient data structure. That's generally what Java's set implementations do.


How to use a Java set: the HashSet

Above, we said that a set was a collection in which an object can be present or not.

Constructing a Set

As with Java collections in general, Set is an interface. When we actually construct a set, we need to pick a specific type.

The usual type of set to choose is the HashSet. The name HashSet comes from the fact that the class uses a technique called hashing to quickly add, find and remove items from the set. As with lists, we can use Java 5's generics feature to specific that we want a set of a particular type of object. So here, we'll create a set of strings:

Set urlsProcessed = new HashSet(500);

We also pass in an estimate of the number of elements that we want to add to the set. We didn't bother with the list (but could and arguably should have done). Giving a number of elements is not essential for collections to work, but can often make them more efficient. It's important to note that this number is just an estimate for the sake of efficiency. It's not an absolute limit, as with an array. We can add more items than our initial estimate.

Adding items to the set...

Now that we have our set, whenever we want to add an item to the set (a string in this case), we call its add() method:

String url = "http://www.javamex.com/";
urlsProcessed.add(url);

...and finding them again

Whenever we want to find out if a particular item is in the set, we use the contains() method:

if (urlsProcessed.contains(url)) {
  // ...
}

And as you might have guessed, whenever we want to remove an item, we can use the remove() method:

urlsProcessed.remove(url);

Common uses for a set

Here, we call our set urlsProcessed. A common use for a set is to remember which items in a list have 'already been seen' so that they are not processed more than once. Imagine a program that spiders web pages by pulling the list of links out of each page it comes across, then going through the linked pages in turn: we need to only process a URL if it hasn't already been processed, otherwise we'd risk going round in an infinitive loop. With our set, we can write something like this to ensure each URL gets processed a maximum of once:

public void processURLs(List urls) {
  for (String url : urls) {
    if (!urlsProcessed.contains(url)) {
      process(url);
      urlsProcessed.add(url);
    }
  }
}

What if I add the same item more than once?

Recall that the point of a set is that it only allows a given item to be added once. If you try and add the same item agan, the add() method will effectively ignore the request. But its return value will tell you if the item was actually added (because it wasn't there before). In the next section, we'll see that we can use this return value to our advantage in certain cases.

A slight performance improvement

The previous example will work fine in many cases. However, it is slightly suboptimal in terms of performance. To check if an item is in the set, the contains() method must make a calculation (specifically, it must calculate something called the hash code). Then, the add() method must also calculate the same hash code to decide where to place the item. Ideally, we'd just like to calculate the hash code once.

Well, we said that we can't add an item to the set more than once, and that the add() method tells us whether or not the item was actually added because it wasn't already there. So if we don't mind adding the URL to the set just as we're going to process it, then we can do the following:

add the item before we decide whether to process it;
look at the return value from add():
if it returns true, that means that the item was added (because it wasn't already in the set), and so we do need to process the URL;
if it returns false, then the item wasn't added this time because it was already there— that obviously means we don't need to process it.
So the code looks something as follows:

public void processURLs(List urls) {
  for (String url : urls) {
    if (urlsProcessed.add(url)) {
      process(url);
    }
  }
}

Enumerating the contents of a set

As well as checking for individual items, we can iterate over all the items in a set with syntax very similar to that of iterating over a list:

System.out.println("URLS processed:");
for (String url : urlsProcessed) {
  System.out.println(url);
}

Recall that a set (and particularly a HashSet) is generally unordered. In other words, when you iterate over the contents of a set as in this example, you won't necessarily get the items out in the same order that you put them in (or in any other well-defined order).

Next...

On the next post, we look at a third type of Java collection, namely the map. Maps are used in all sorts of programming situations where we want to create associations between objects.

Lists (Java Collections)

What is a List in Java?

When we refer to a list in Java, we mean specifically a collection of objects that:

has a fixed order (when we add an object to the list, it will stay in the place we put it);
allows objects to be referred to by position, so we can get or set the "4th element in the list";
generally speaking, list does not have a fixed number of elements, unlike an array.

A plain old array has the first two of these properties, but not the third: when we create an array, we always have to say how many elements it has, and we can't change this number once the array is created. The third property isn't strictly speaking a necessary property of a Java List. But in practice, the most commonly used types of List are used instead of a plain old array because they have this "unbounded" property.

Using a List in Java:

As with Java collections generally, there isn't actually a single Java class called List. Instead, there is an interface called List, with various implementations. So a typical way to create a list would look like this:

import java.util.*;

List myList = new ArrayList();

In the above example, we import all classes from java.util, which is where List and ArrayList reside. In this example, the actual collection object that we create is an ArrayList. This is a list implementation that stores objects inside an array. Although arrays have to be fixed-size, ArrayList internally handles this by creating a new, bigger array where necessary and copying the previous elements into the new array. So to the caller, what we effectively get is a list with no fixed size which we can add to and remove from arbitrarily.

Notice that we also state, inside angle brackets, that the list will specifically hold objects of type String. If you haven't come across it before, this syntax was introduced in Java 5, part of what is technically called the generics framework.

Now we have our list, we can start doing interesting things with it such as adding and removing elements. Any List provides various methods, including add(), get(), size():

myList.add("Hello");
myList.add("Hello");
myList.add("world");
System.out.println("The list contains " +
   myList.size() + "elements, and " +
   "the first is " + myList.get(0));

Lists provide various other useful methods, such as for removing items from the list, adding at a specific position, or determining the first or last position of a particular item in the list.

Using collections in Java: enumerating items in a list:

Above, we began our tour of Java collections by looking at creating and using an ArrayList. We saw an example of how to add an item to the list, query the list's size (number of elements currently in the list) and fetch the nth element.

Another commonly needed operation is to enumerate or iterate through all of the items in the list. Now, one way we could do this would be with a plain old for loop: query the number of elements in the list, and then cycle through from 0 to that number minus one, pulling out the nth element on each cycle through the loop:

List myList = ...

for (int len = myList=size(), i = 0; i < len; i++) {
  String s = myList.get(i);
  System.out.println("Item " + i + " is " + s);
}

Note that rather than calling the size() method on every pass through the loop, we can read the size once and store it in a local variable. If anything, this is more of a programming idiom than a real performance gain: the overhead of calling size() isn't much for most collections, especially with modern JVMs that can inline the call.

A disadvantage of the method we just mentioned is that it assumes that for a particular list, the cost of finding the nth element is negligible. That's the case for an ArrayList, but not for a LinkedList, which has to 'cycle through the chain' to find the object at a given "index". From Java 5 onwards, the compiler can help us out by allowing us to use a special loop syntax:

for (String s : myList) {
  System.out.println("Next item: " + s);
}

The above code will create a loop that cycles through all the elements in the list, and on each cycle assigns the next element in the list to the variable s. Under the hood, the compiler will generate code that iterates through the list by effectively asking the list which iteration method to use.

Java Collections

Collections in Java

A collection is a general term that means something like "a bunch of objects stored in a structured manner". Java has various standard collection classes and using collections in Java allows you to organise data in memory in various convenient ways. Examples might include:

a simple list of strings;
a mapping or association of strings to strings (e.g. country names to the names of their capitals);
a list that imposes some constraint, e.g. keeping strings in alphabetical order, or not allowing duplicates in the list.
The Java Collections Framework— often called simply (Java) Collections— is a library of classes that implement these and various other data structures. The collections framework also provides utility methods to perform functions such as sorting a list of data.


Collections Interfaces:

1. Collection Interface.
2. List Interface.
3. Set Interface.
4. SortedSet Interface.

Collections Classes:

1. AbstractCollection.
2. AbstractList.
3. AbstracSequentialtList.
4. LinkedList.
5. ArrayList.
6. AbstractSet.
7. HashSet.
8. LinkedHashSet.
9. TreeSet.

Legacy Classes & Interfaces:

1. Enumeration interface.
2. Vector.
3. Stack.
4. Dictionary.
5. Hashtable.
6. Properties.
7. Using store() & load().

Other Important stuff in Collections Framework:

1. Accessing a Collection via an Iterator.
2. Storing User defined Classes in Collections.
3. Random Access Interface.
4. Map Interfaces & Classes.
5. Comparators.
6. Collections Algorithms.